做了一天做完了发现做法和之前的题解不一样。
子任务 $1,2$ 都很简单。设 $n,m$ 同阶，下面想一个 $n^4$ 或 $n^3$ 的做法。
定义在位置 $x$ 向左扫一次为进行 $a_x \leftarrow a_x-c$，再进行 $\forall i \in[1,x],a_i\leftarrow a_i-1$。定义在位置 $x$ 向右扫一次为进行 $a_x \leftarrow a_x-c$，再进行 $\forall i \in[x,n],a_i\leftarrow a_i-1$。
首先观察一个简单但是关键的结论：对于一次在 $x$ 位置向左扫与一次在 $y$ 位置向右扫，若有 $x
所以最优策略一定存在一个分界点 $x$，在 $x$ 左侧全是向右扫，在 $x$ 右侧全是向左扫。而 $x$ 处可以同时有向左和向右扫。发现确定一侧被全局扫 $1$ 的次数后，可以从外往里贪心获取把这一侧扫光所需的次数。
此时我们可以考虑枚举分界点。发现需要预处理每个前缀 $i$，被从分界点后面的往前扫 $j$ 次之后需要再向后扫多少次才能扫干净这个前缀。后缀同理。设为 $f_{i,j}$ 与 $g_{i,j}$。
那么我们可以枚举分界点 $x$，再枚举前面往后面扫的次数 $j$ 与后面往前面扫的次数 $k$。
则我们至少需要使用的操作次数为 $\max(j,g_{i+1,k})+\max(k,f_{i-1,j})$。发现如果 $g_{i+1,k} > j$，则可以将 $j$ 变大，这时第二项不会变大，不劣。$f_{i-1,j}>k$ 同理。
此时我们可能会有多出来的几次操作，这几次都在 $x$ 上做。其余都是跨过 $x$。所有操作在 $x$ 位置总共扫掉了 $(j + k) \times (c + 1) - (f_{i - 1,j} + g_{i + 1,k}) \times c$ 的雪。由于最后我们要把整个序列扫干净，则必须有 $(j + k) \times (c + 1) - (f_{i - 1,j} + g_{i + 1,k}) \times c\ge a_x$。
所以我们对满足条件的 $x,j,k$ 算出答案即可。这样做预处理两维，枚举三维，复杂度是 $O(n^3)$。
继续观察，发现在 $x,j$ 确定的时候，可行的 $k$ 是一个后缀。由于答案为最小的 $j+k$，则只需要找到可行的最小 $k$ 即可。此时二分即可做到 $O(n^2\log n)$。
更进一步，发现对于同一个 $x$，当 $j$ 增大的时候，可行的最小的 $k$ 不会减小只会增大。使用双指针维护即可做到 $O(n^2)$。
接下来尝试做到小于 $O(n^2)$ 的复杂度。
打表发现如果还要枚举分界点，则内层最优的 $j$ 转移点看不出来性质，只能枚举。
所以考虑不枚举分界点。发现枚举 $j,k$ 也能做。具体的，预处理 $l_{x,y}= (p,k)$，表示进行 $y$ 次全局 $-1$ 后再做 $x$ 次后缀减，最多能把 $a_{p-1}$ 及之前的减到 $0$，而 $a_p$ 被减了 $k$ 次。预处理 $r_{x,y}$ 表示进行 $y$ 次全局 $-1$ 后再做 $x$ 次前缀减，最多能把 $a_{p+1}$ 及之前后的减到 $0$，而 $a_p$ 被减了 $k$ 次。
考虑枚举 $x,y$。发现一个 $x,y$ 合法，当且仅当 $l_{x,y}(p) > r_{y,x}(p)$ 或 $l_{x,y}(p) = r_{x,y}(p),(l_{x,y}(k) + r_{x,y}(k)) \times c + x + y \ge a_{l_{x,y}(p)}$。直接枚举并判断合法即可。对于一个合法的 $x,y$，此时需要的次数为 $x+y$。
观察发现此时可行的最小 $y$ 随着 $x$ 增加而不降。可以双指针维护。
此时有了预处理 $O(n^2)$，计算答案 $O(n)$ 的做法。
此时我们可能尝试使用可持久化数据结构快速维护出所有的 $l$ 与 $r$。但是我不会。转而研究对于一个 $l_{x,y}$，$x$ 或 $y$ 变化 $1$ 时 $(p,k)$ 的变化。
考虑维护全局 $-y$ ，做 $x$ 次向左扫或向右扫后的序列（不对 $0$ 取 $\max$）。
先考虑全局 $-y$，向右扫 $x$ 次的序列。
当 $x\leftarrow x+1$ 时，多了一次向右扫。则会在 $p$ 处进行一次向右扫。进行一次单点 $-c$，后缀 $-1$。然后更新 $(p,k)$。
当 $x\leftarrow x-1$ 时，少了一次向右扫。则会撤销最后一次扫雪并更新 $(p,k)$。
当 $y\leftarrow y+1$ 时，多了一次全局 $-1$，则进行全局 $-1$，并在第一个被扫过且 $\le -c-1$ 的地方撤销一次向右扫。如果成功撤销，则找到最后一个 $>0$ 的地方进行向右扫。
当 $y\leftarrow y-1$ 时，少了一次全局 $-1$，则进行全局 $+1$，并撤销最后一次操作，放在第一个 $>0$ 的地方。即撤销最后一次向右扫，然后在第一个 $>0$ 的地方进行一次向右扫。
全局 $-y$，向左扫 $x$ 次的序列同理。
这个东西看起来就不好用数据结构快速维护出所有的值。
但是注意到 $x,y$ 总的移动量是 $O(n)$ 的。所以我们可以直接维护正着全局 $-y$，扫 $x$ 次与反着全局 $-x$，扫 $y$ 次的序列，每次移动端点判断是否合法即可。
总复杂度 $O(n\log n)$。常数挺大，注意精细实现。