自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

搬运于2025-08-24 23:00:15，当前版本为作者最后更新于2024-07-04 21:57:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们把 P 看成 $1$，C 看成 $0$。

如果只有一行，那么代价肯定是 $0,1$ 顺序对数量，换个容易计算的描述，设有 $c$ 个 $1$，下标和为 $s$，那么代价就是 $s-\frac{c(c+1)}{2}$。

有两行的时候，我们一定可以先通过一些操作把第二行的 $1$ 交换到第一行，然后再两行分别按照一行的时候求和。

设最终第一行有 $c_1$ 个 $1$，第二行有 $c_2$ 个 $1$，那么代价就是 移动次数加上 $1$ 的下标和减去 $\frac{c_1(c_1+1)+c_2(c_2+1)}{2}$。

移动次数里，上下移动的次数是确定的，而注意到我们对于一个第二行的 $1$，它一定去找第一行最靠左的 $0$ 填进去不劣，对称的同理。

因此我们一定是把第二行的后缀的一些 $1$ 填到了第一行一些前缀的 $0$ 里。

考虑一个 $1$ 往左移动的时候，因为每步下标减一，所以相当于代价不变还等于原来的坐标，如果往右走，则每次代价加 $2$。

考虑一条 $(i,i+1)$ 被向右跨过的次数，化简一下可以发现是 $\max(0,sum_i-i-c_2)$，其中 $sum_i$ 为前 $i$ 列里两行一共多少个 $1$。

那么我们直接开线段树维护每个 $c_2$ 对应的答案 $ans_{c_2}$，上下交换不影响 $sum_i$，左右交换最多改变一列的 $sum_i$，表现在 $ans$ 上就是区间加减，因此可以直接维护。

复杂度 $O(n\log n)$。