题解

本题使用分奇偶枚举 + 贪心计数求解绳索染色问题。

算法思路：

1. 问题观察：

   • 相邻绳索颜色不能相同
   • 对于每种颜色，计算最少需要改变多少根绳索才能使该颜色合法
   • 如果位置 $i$ 和 $i+1$ 颜色相同，则必须改变其中一根

2. 分奇偶处理：

   • 奇数位置冲突：位置 $(1,2), (3,4), (5,6), \ldots$
   • 偶数位置冲突：位置 $(2,3), (4,5), (6,7), \ldots$
   • 分别枚举奇数和偶数位置的冲突，计算最优解

3. 维护颜色出现次数：

   • 使用 bin[i] 记录颜色 $i$ 当前出现的次数
   • 使用 cnt[j] 记录出现次数为 $j$ 的颜色个数
   • mx 记录当前最大的出现次数

4. 删除颜色 $i$ 后的最优策略：

   • 删除颜色 $i$ 的所有绳索：数量为 $sz[i]$
   • 删除与颜色 $i$ 相邻的冲突绳索
   • 剩余绳索中，选择出现次数最多的颜色 $mx$
   • 答案为：$n - sz[i] - mx$（需要改变的绳索数）

5. 动态维护：

   • 使用 add 和 del 函数动态维护颜色的出现次数
   • 删除时如果最大值只有一个，需要更新 mx

时间复杂度：$O(n + m \cdot deg)$，其中 $deg$ 是平均邻接边数。

#include<bits/stdc++.h>
#include<ctime>
using namespace std;

namespace Smilemask{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef pair<int,int> PII;
	#define rd read()
	inline int read(){
		int num=0,sign=1;char ch=getchar();
		while(!isdigit(ch)){if(ch=='-'){sign=-1;}ch=getchar();}
		while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
		return num*sign;
	}

	const int N=1e6+10;

	int n,m,c[N],sz[N];
	int mx,ans[N],cnt[N],bin[N];
	vector <int> G[N];

	void add(int x){
		cnt[bin[x]]--;
		cnt[++bin[x]]++;
		mx=max(mx,bin[x]);
	}

	void del(int x){
		if(mx==bin[x]&&cnt[bin[x]]==1)
			mx=bin[x]-1;
		cnt[bin[x]]--,cnt[--bin[x]]++;
	}

	void solve(int t){
		for(int i=1;i<=n;i++){
			bin[i]=cnt[i]=0;
			G[i].clear();
		}
		for(int i=1;i<=n;i++)
			add(c[i]);
		for(int i=t;i<=n;i+=2){
			int A=c[i],B=c[i+1];
			if(A==B) continue;
			G[A].push_back(B);
			G[B].push_back(A);
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=sz[i];j++)
				del(i);
			for(int j:G[i])
				del(j);
			ans[i]=min(ans[i],n-sz[i]-mx);
			for(int j:G[i])
				add(j);
			for(int j=1;j<=sz[i];j++)
				add(i);
		}
	}

	void Main(){
		n=rd,m=rd;
		for(int i=1;i<=n;i++)
			c[i]=rd,sz[c[i]]++;
		for(int i=1;i<=m;i++)
			ans[i]=1e9;
		solve(1),solve(2);
		for(int i=1;i<=m;i++)
			cout<<ans[i]<<endl;
	}		
}

int main(){
	Smilemask::Main();
	return 0;
}