题意

N 个布丁摆成一行,进行M次操作.
每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.
例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

题解

注意可能出现把a改成b后再改回来的情况

首先一个最简单的暴力就是每个颜色用一个vector保存位置，修改时把所有要修改的布丁暴力插入到目标颜色的vector里。

然后注意到可以用启发式优化，修改时把小的插到大的里。

可以开一个数组$dic$记录每个颜色的真实颜色，初始时$dic[i]=i$

如果目标颜色比修改颜色小，那么就$swap(dic[a],dic[b])$

修改前先$a=dic[a],b=dic[b]$

代码

#include 
#include 
#include 
#include 
using namespace std;
#define N 1000001
#define now q[a][i]
int fa[N],col[N],dic[N];
bool vis[N];
vector q[N];
int main()
{
	int n,m,cnt;
	cin>>n>>m;
	cnt=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&col[i]);
		q[col[i]].push_back(i);
		if(col[i]==col[i-1]) cnt--;
	}
	for(int i=1;iq[dic[b]].size());
			if(flag) swap(dic[a],dic[b]);
			a=dic[a],b=dic[b];
			for(int i=0;i