自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:15:11，当前版本为作者最后更新于2025-05-01 18:21:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

• 作为一段前缀出现。
• 作为一段后缀出现。
• 完整出现。
• 自己把子段包含住。

都是好统计的，可以做到线性。难的是 $m=2$。首先你套路性将奇数位翻转，那么一个子段的操作次数就是 $1$ 的个数与 $2$ 的个数的最小值。设这俩为 $c_1,c_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);
}