P12263 『STA - R9』回听

给定一个长为 $n$ 的序列 $a$，定义回听操作如下： > 定义一次回听操作为，任意选择一个 $x\in [1,n]$，然后进行任意次（可以是 $0$ 次）如下操作： > > - $a_x \leftarrow \max\{a_x-1,0\}$，选择一个 $j\in[1,x)$，交换 $a_x,a_j$ 并令 $x \leftarrow j$。 > > 定义 $b_i$ 为进行一次回听后 $a_i$ 的最小值。 > > 注意此处回听操作不会实际影响序列 $a$ 的值。可以认为操作之后 $a$ 会恢复到操作之前的状态。 序列会进行 $m$ 次修改操作，每次给定 $l,r,v$，使 $a_l$ 到 $a_r$ 中的每个数增加 $v$。每次修改后你需要输出进行一次回听操作后本质不同的 $b_i$ 共有多少个（$b_i$ 与 $b_j$ 本质不同当且仅当 $b_i \ne b_j$）。 **注意：修改操作间相互影响，回听操作间相互独立。**

无

无

**【操作解释】** 对于序列 $\{3,8,2,4,7\}$，对它进行回听操作的过程如下： 若选择 $x=5$，进行 $3$ 次操作，选择的 $j$ 分别为 $4,2,1$，那么整个序列会这样变化： - $\{3,8,2,4,7\}$ - $\{3,8,2,6,4\}$ - $\{3,5,2,8,4\}$ - $\{4,3,2,8,4\}$ **【样例 $1$ 解释】** 修改操作后序列 $a$ 变为 $\{ 2,3,3\}$。 当 $i=1$ 时，选择 $x=3$，进行 $2$ 次操作，$j$ 分别选择 $2,1$，得到 $b_i=a_3-1-1=1$。 当 $i=2$ 时，选择 $x=2$，进行 $1$ 次操作，选择 $j =1$，得到 $b_i=a_1=2$。 当 $i=3$ 时，选择 $x=3$，进行 $1$ 次操作，选择 $j =1$，得到 $b_i=a_1=2$。 综上，序列 $b$ 为 $\{ 1,2,2\}$，故答案为 $2$。 **【数据范围】** **本题采用捆绑测试。** - Subtask 0（10 pts）：$1\le n,m \le 10$。 - Subtask 1（15 pts）：$1\le n,m \le 10^5$，$l\ge 2$，$a_1=1$，$\forall i\in[2,n],\,a_i>i$。 - Subtask 2（15 pts）：$1\le n,m \le 1000$。 - Subtask 3（30 pts）：$1\le n,m \le 10^5$。 - Subtask 4（30 pts）：无特殊限制。 对于所有测试数据，保证 $1\le n,m\le 5\times10^5$，$1\le a_i,v\le 10^6$，$1\le l\le r\le n$。 **本题输入输出量较大，建议使用较快的 IO 方式。**