CEOI2024 Segregacija
我们把 P 看成 \(1\)，C 看成 \(0\)。
如果只有一行，那么代价肯定是 \(0,1\) 顺序对数量，换个容易计算的描述，设 \(c\) 个 \(1\)，下标和为 \(s\)，那么代价就是 \(s-\frac{c(c+1)}{2}\)。
有两行的时候，我们一定可以先通过一些操作交换两行，然后再两行分别按照一行的时候求和。
设最终第一行有 \(c1\) 个 \(1\)，第二行有 \(c2\) 个 \(1\)，那么代价就是 移动次数加上 \(1\) 的下标和减去 \(\frac{c1(c1+1)+c2(c2+1)}{2}\)。
移动次数里，上下移动的次数是确定的，而注意到我们对于一个第二行的 \(1\)，他一定去找第一行最靠左的 \(0\) 填进去不劣，因此我们一定是把第二行的后缀的一些 \(1\) 填到了第一行一个前缀的 \(0\) 里。
考虑一个 \(1\) 往左走的时候，因为每步下标减一，所以相当于代价不变还等于原来的坐标，如果往右走，则每次代价加 \(2\)。
考虑一条 \((i,i+1)\) 被向右跨过的次数，化简一下可以发现是 \(\max(0,sum_i-i-c2)\)，其中 \(sum_i\) 为前 \(i\) 两行一共多少个 \(1\)。
那么我们直接开线段树维护每个 \(c2\) 对应的答案，上下交换不影响 \(sum_i\)，左右交换最多改变一个，表现在答案数组上就是区间加减，因此可以直接维护。
复杂度 \(O(n\log n)\)。
标签：sum,CEOI2024,第二行,Segregacija,代价,c2 From： https://www.cnblogs.com/jesoyizexry/p/18277020