题解

思路

令 $s_{t,i}$ 表示前 $t$ 次操作对第 $i$ 项累计增加的数值。

做法

任意时刻保持 $A_i<A_{i+1}$ 等价于初始时满足 $A_i+(s_{t,i}-s_{t,i+1})<A_{i+1}$。因此对每个相邻位置，只需令 $c_i=\max_t(s_{t,i}-s_{t,i+1})$，其中初始时刻保证 $c_i\ge0$；所有约束合并为 $A_{i+1}\ge A_i+c_i+1$。

最小方案显然取 $A_1=1$，随后令每个不等式取等。处理一次对位置 $p$ 的加法时，差值 $p$ 增加 $x$，差值 $p-1$ 减少 $x$，只需更新这两个差值及其历史最大值。最后从左到右构造最小 $A$ 并累加。

复杂度

时间复杂度为 $O(N+Q)$，空间复杂度为 $O(N)$，答案使用 64 位整数。