题解

简化一下题意，给定 $m$ 个操作，每次给$[l, r]$ 区间减去 $h$ ，问第几次操作会满足当前位置的数 $< 0$

看到这种区间加减的问题，在笔试中，一般可以启发我们用差分解决。

这题可以考虑二分答案后差分，每次二分操作次数 $mid$，然后进行 $mid$ 操作后，判断当前 $a[i]$ 是否满足条件即可

时间复杂度为 : $O(n \log n)$

问题描述

小红有一项特殊技能，可以降低连绵山峰的高度。每次施法，他能够选定一段连续的山峰区域，使得这些山峰的高度均匀降低。现在他想知道，通过有限次施法之后，何时能使得至少有一个山峰的高度降至海平面以下（高度小于等于 0）。已知山峰的数量和施法的次数，请计算出何时可以实现目标。

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示山峰的数量和施法的次数。

第二行包含 $n$ 个正整数 $H_1, H_2, ..., H_n$，表示每个山峰的初始高度。

接下来的 $m$ 行，每行包含三个正整数 $L_i, R_i, h_i$，表示每次施法作用的山峰区间 $[L_i, R_i]$ 和降低的高度 $h_i$。

输出格式

输出一个整数，表示在第几次施法之后，至少有一个山峰的高度降至海平面以下。

样例输入

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

样例输出

3

评测数据与规模

• 对于 $1 \le n, m \le 10^5$，$1 \le h_i, H_i \le 10^9$，$1 \le L_i \le R_i \le n$ 的输入数据，保证有解。