谷仓分配(Barn Allocation)

题目描述

农夫约翰最近开了一个新的牲口棚。因为其中的一些畜栏风景更好，所以奶牛们向约翰发出了希望分配畜栏的申请。

牲口棚有 $N$ 个畜栏 $(1 \le N \le 100,000)$，方便起见，我们把它们编号为 $1 \sim N$，畜栏 $i$ 能容纳 $C_i$ 头牛 $(1 \le C_i \le 100,000)$。第 $i$ 头牛申请为它分配 $A_i$ 到 $B_i$ 的编号连续的畜栏来让它散步 $(1 \le A_i \le B_i \le N)$。换言之，这头奶牛希望能自由地访问畜栏 $A_i \sim B_i$，而为了满足它的要求，你需要在 $A_i \sim B_i$ 范围内的畜栏中为它预留至少一单位容量。

给出 $M$ 个畜栏分配请求 $(1 \le M \le 100,000)$，回答最多能满足多少头牛的要求而不增加额外的畜栏。

输入格式

第一行包括两个以空格隔开的正整数：$N,M$。

第二行到第 $N+1$ 行：第 $i+1$ 行每行包括一个整数：$C_i$。

第 $N+2$ 到第 $N+M+1$ 行：第 $i+N+1$ 行每行包括两个整数 $A_i,B_i$。

输出格式

仅一行：能满足的最大要求数。

样例输入 #1

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

样例输出 #1

3

数据范围

考虑以下例子：

畜栏号:      1   2   3   4   5
           +---+---+---+---+---+
容纳空间:   | 1 | 3 | 2 | 1 | 3 |  
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)

约翰显然不能满足所有的需求，因为畜栏 $3,4$ 请求太多了。

经过试验，我们发现，我们能满足牛 $1,3,4$ 的需求，所以这组数据答案为 $3$。

Source: USACO 2010 March Gold

对于 $100\%$ 的数据，$1 \le N, M \le 10^5$，$1 \le C_i \le 10^5$，$1 \le A_i \le B_i \le N$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1750。

测试点分布

出处：原题链接