题解：P10684 [COTS/CETS 2024] 分割 Segregacija

Larunatrecy · 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)。