ARC126E

shiruoyu114514 · 2025-05-11 21:20:55 · 题解

脑电波题。

断言：令 D = \sum \limits_{i=1}^n \sum \limits_{j=1}^n |a_i-a_j|，即每个点到其它所有点的距离之和，则答案为 \frac{1}{4}D。

证明：我们可以把每次操作拆成若干次操作，使得每次操作过后，不会有一对 p,q 满足在操作前有 a_p<a_q，在操作后有 a_p>a_q。

当我们操作下标 i,j(a_i<a_j) 相互靠近 x 距离时，由于只有 i,j 被改了，所以受到影响的只有所有点与 i,j 之间的距离。

对于 i 左边的数 l，即 a_l<a_i，贡献为 a_i-a_l+a_j-a_l。由于 a_i \leftarrow a_i+x，a_j \leftarrow a_j-x，所以 l 的贡献不会改变。

对于中间的数 m，即 a_i<a_m<a_j，贡献为 a_m-a_i+a_j-a_m=a_j-a_i，变化后 m 的贡献会减少 2x。

对于右边的数 r，即 a_j<a_r，贡献为 a_r-a_i+a_r-a_j，变化后 r 的贡献不变。

而 i,j 本身的贡献会减少 4x。

所以每次贡献至少减少 4x，并且当且仅当中间没有数，即 i,j 相邻时取等。

于是得证。

单点修改并维护每个点的贡献时，我们只需要分别知道左边的数的个数与和值，右边的个数与和值即可。权值线段树维护即可。时间复杂度 O(n \log n)。