题解 CF1051G 【Distinctification】

## 题意： 给了 $n$ 个数对 $(A,B)$。 你可以若干次操作。 $1. A_i = A_i + 1, cost\ B_i [A_i = A_j, i != j]$。 $2.A_i = A_i - 1, cost\ -B_i [A_i = A_j + 1, i != j]$。 ## solution: 如果 $A_i$ 互不相同，存在 $A_i = A_j + 1$,那么显而易见可以交换两个数，代价是 $B_i - B_j$。 所以最后序列会被分成 $A_i$ 的若干段，且每段 $B$ 递减。 如果 $A_i$ 有可能相同，那么我们找一个最近的，使得互不相同，这个右端点可以用并查集维护，再同样操作。 设 $A_i$ 变成了 $A_i'$，那么我们发现 $A_i$ 的贡献其实是 $(A_i'-A_i) \times B_i$，然后我们维护所有数的贡献，也就是 $\sum_i (A_i' - A_i) \times B_i$。 所以我们只需要以 $B_i$ 作为下标做线段树。 最后 $B_i$ 一定是递减的，那么贡献是左区间的 $B_i$ 乘上右区间的个数。 然后加入一个 $A_i$ 时，先减掉原来的贡献，合并之后再算一下贡献，这题就做完了。