P10071 [CCO 2023] Triangle Collection

Alice 有一些棍子。一开始，对于每个 $l=1, \ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。 Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。 有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $l_{i}$ 和 $d_{i}$，表示长度为 $l_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $l$ 的棍子。 你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。

第一行包含两个用空格分隔的整数 $N$ 和 $Q$。 第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。 接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $l_{i}$ 和 $d_{i}$，表示一个事件。 保证在每个事件之前和之后，对于每个 $l=1, \ldots, N$，长度为 $l$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。

输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。

在第一个事件之后，Alice 可以用长度为 $ (1,1,1)$ 的棍子做一个三角形。 在第二个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形。 在第三个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形，并用长度为 $(2,2,3)$ 的棍子做一个三角形。 对于所有的数据，有 $1 \leq N, Q \leq 2\times 10^5$，$0 \leq c_{i} \leq 10^{9}$，$1 \leq l_{i} \leq N$，$-10^{9} \leq d_{i} \leq 10^{9}$。 |子任务编号| 分值| N, Q 的范围| 额外限制| | :-: | :-: |:-:|:-:| |1| 20| $1 \leq N, Q \leq 2000$| 在所有时刻，总共最多有 $2000$ 根棍子。| |2| 20| $1 \leq N, Q \leq 2000$|没有额外的限制| |3| 20| $1 \leq N, Q \leq 2\times 10^5$| 在所有时刻，每种长度的棍子的数量只会是 $1,2,3$ | |4| 20| $1 \leq N, Q \leq 2\times 10^5$| $d_{i}=1,-1$ | |5| 20| $1 \leq N, Q \leq 2\times 10^5$|没有额外的限制|