题解：P12391 「RiOI-6」帝国少女

· · 题解

直接对一个子段暴力是典题。若 m=2 序列只有可能 1,2 交替，枚举两种情况算操作次数最小值即可。对于 m>2，一段长度为 l 的极长同色段最少需要操作 \lfloor l/2\rfloor 次，全加起来就是答案。

然后考虑原题，你需要对所有子段求和。对于 m>2 是简单的，原序列中的同色段只有以下四种情况：

都是好统计的，可以做到线性。难的是 m=2。首先你套路性将奇数位翻转，那么一个子段的操作次数就是 1 的个数与 2 的个数的最小值。设这俩为 c_1,c_2。你实际上会发现：

\min(c_1,c_2)=\frac{c_1+c_2-|c_1-c_2|}2

所以你将所有 2 替换成 -1，问题转化为所有子段和的绝对值之和。前缀和一下变成任意两数差的绝对值之和，排个序做就好了。容易发现值域是 [-n,n]，桶排可以做到线性，没啥必要就是了（双关）。

其中一个验题人认为本题是紫题并提出了一个分块做法。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

int n, m, a[MAXN], s[MAXN]; ll sum, ans;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if (m == 2) {
        for (int i = 1; i <= n; i++) a[i]--, (i & 1) && (a[i] ^= 1);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + (a[i] ? 1 : -1);
        sort(s, s + n + 1);
        for (int i = 1; i <= n; i++) ans += (ll)i * (n - i + 1); 
        for(int i = 0; i <= n; i++) ans -= (ll)s[i] * i - sum, sum += s[i];
        printf("%lld", ans >> 1); return 0;
    }
    for (int i = 0, k = 0; i <= n; i++) {
        if (a[i] == a[i + 1]) { k++; continue; }
        for (int j = 1; j < k; j++) ans += (ll)j / 2 * (k - j + 1);
        ans += (ll)k / 2 * (i - k + 1) * (n - i + 1);
        for (int j = 1; j < k; j++) ans += (ll)j / 2 * (n - k);
        k = 1;
    }
    printf("%lld", ans);
}