题解：CF1884E Hard Design

__staring__ · 2026-04-24 11:07:55 · 题解

提供一篇与其他题解略有不同的做法。

首先令 a_i\larr \max\{a_n\}-a_i，这样限制变为可以区间 -1 使所有元素为零。为方便起见，选择一个 a_0=0 的循环移位计算初始答案。

对于 p_1\le p_2\le p_3\le p_4，由于 (p_3-p_1+1)^2+(p_4-p_2+1)^2\le(p_4-p_1+1)^2+(p_3-p_2+1)^2，所以操作之间只有包含或不交，形成树形结构。

于是按值域从大到小扫描线，设当前为 v，那么序列 b_i=[a_i\ge v] 的极长 1 区间都需要操作。注意到本质不同的操作只有 O(n) 种，于是有一个 O(n\log n) 的做法是：

初始用大根堆维护所有连续段 (v,l,r)（按此顺序比较）。取出堆顶 (v,l,r)，如果新堆顶 (v',l',r') 满足 v'=v\wedge r'=l-1 那么合并为 (v,l',r)。不可合并后，记 t=\max(a_{l-1},a_{r+1})，那么有 v-t 个 [l,r] 的操作，计算其贡献。若 t\ne0 将 (t,l,r) 放入大根堆。

上述做法可以通过此题。考虑优化，注意到若把上述流程放到小根笛卡尔树上考虑，则相当于每个节点的操作区间是其子树，操作次数为其值与父节点的差。于是可以单调栈对每个连续段 v 找出左右第一个 <v 的位置 l,r，则有 v-\max(a_{l-1},a_{r+1}) 个 [l+1,r-1] 的操作。

计算完初始答案后，考虑环上移位会切开一些区间。以 i 开头时切开的区间 [l,r] 满足 i\in[l+1,r]，其贡献增量前者为 1，后者为 (i-l)^2+(r-i+1)^2-(r-l+1)^2=-2(i-l)(r-i+1)=2(i^2-(l+r+1)i+l(r+1))。于是每个区间计算贡献时只需做三次区间加，差分前缀和即可快速维护。

总复杂度 O(n)。Submission - Codeforces。