CF1884E Hard Design 题解

先考虑如果没有循环移位操作的话怎么做。把序列倒过来，记 $\text{lim}$ 为整个序列内所有元素的最大值，则先执行操作 $a_i\leftarrow\text{lim}-a_i$ 然后把区间加 $1$ 看作是区间减 $1$，终止条件看作是序列内所有元素均变为 $0$ 即可。

第一问就是积木大赛，显然答案为 $\sum\limits_{i=1}^n\max(a_i-a_{i-1},0)$。第二问可以笛卡尔树分治做到 $O(n)$ 或 $O(n\log n)$ 的时间复杂度，但是笛卡尔树分治的结构比较复杂难以刻画，因此考虑换一个方向：注意到对区间 $[l,r]$ 执行一次操作的代价是 $(r-l+1)^2$，因此考虑拆贡献，对每一个二元组 $(i,j)$ 满足 $l\le i,j\le r$ 分别对答案做出 $1$ 的贡献。

此时考虑什么时候 $i,j$ 可以为答案做出 $1$ 的贡献：很显然当且仅当对一个区间 $[l,r]$ 做操作时，$l\le i,j\le r$ 才会做出 $1$ 的贡献。反过来统计贡献次数就是 $\min\limits_{k=\min(i,j)}^{\max(i,j)}a_k$。对所有 $i,j$ 的贡献求和就可以得到第二问的答案：

换个方式表示答案：

用单调栈处理内层 $a_k$ 的贡献区间即可做到 $O(n)$ 求解。具体的，记 $L_i$ 表示 $a_i$ 作为区间最小值可以贡献到的左端点，$R_i$ 表示 $a_i$ 作为区间最小值可以贡献的右端点，则 $a_k$ 对后半段和式的贡献即为 $a_k(2(k-L_k+1)(R_k-k+1)-1)$。

此时直接暴力对 $a$ 数组的每个循环移位求答案时间复杂度为 $O(n^2)$，考虑优化。容易想到先破环成链，此时贡献的变化仅限于在区间开头删除一个元素 / 在区间末尾添加一个元素。容易发现 $k-L_k$ 和 $R_k-k$ 的变化都形如常数 - 一次函数的分段函数形式，因此直接分类讨论然后差分存答案即可。

总时间复杂度为 $O(n)$，但是代码写起来比较痛苦。