思路：哈希表模拟

这道题如果使用线段树那就是变复杂了，可以观察到答案是具有二段性的，所以可以考虑将答案二分，那么我们假设当前要修改到第x版计划，那么要怎么快速知道修改到第x版计划后是否有人的怒火值超过阙值呢，因为每一次修改只会对一段人的怒火值全部加1，那么我们就可以使用差分，O(1)的进行加减，当修改完第x版计划后进行前缀和一一比对是否超出阙值即可

时间复杂度:$O(nlogm)$

代码

def check(x):
    b = [0] * (n + 100)
    for i in range(1, x + 1):
        x1 = mb[i][0]
        x2 = mb[i][1]
        b[x1] += 1
        b[x2 + 1] -= 1
    for i in range(1, n + 1):
        b[i] += b[i - 1]
        if b[i] > a[i]:
            return False
    return True

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
mb = [0] * (m + 1)
for i in range(1, m + 1):
    mb[i] = tuple(map(int, input().split()))

l = 0
r = m

while l < r:
    mid = (l + r + 1) // 2
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(l)

题目描述

小红正在做一个工程，她先写了份初版工程计划，但是经理不太满意，让小红改一改。

改着改着，小红就改了$32$ 版设计方案，然后经理说，还是用初版工程计划吧，现在小红非常的.....

小红小组内有$n$个人，大家一起完成了一个初版工程计划，初始时大家的怒火值都是 $0$。

但是经理对工程计划并不满意，共需要修改m次工程计划，每次修改会先让第l到r个人的怒火值加 $1$，然后再修改工程计划。

组内每个人都有一个怒火阈值$a$，一旦第i次修改时有人怒火值大于怒火阈值，他就会去找经理对线，直接将最终的工程计划定为第$i-1$版工程计划，并且接下来工程计划都不需要再修改了。

小红想知道，最终会使用第几版工程计划。初版工程计划被认为是第$0$版工程计划。

输入描述

第一行输入两个整数$n,m(1 \leq n,m \leq 10^5)$表示数组长度和修改次数。

第二行输入$n$个整数表示数组$a(0 \leq a \leq 10^5)$

接下来$m$行，每行输入两个整数$l,r(1 \leq l \leq r \leq n)$

输出描述

输出一个整数表示答案

样例

输入

2 3
2 2
1 1
1 2
2 2

输出

3

说明

改为三次计划，大家的怒火度都为$2$，都不超过怒火阈值，所以使用最后一版计划。