```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read()
{
int a = 0,x = 1;char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
return a*x;
}
const int N=3e6+7;
int n,m,ans;
int siz[N],h[N],p[N];
int f[N],c[N],que[N];
void merge(int a,int b)
{
for(int i = h[a];i;i = p[i]) ans -= (c[i-1] == b) + (c[i+1] == b);
int j;
for(int i = h[a];i;i = p[i]) c[j=i] = b;
siz[b] += siz[a],siz[a] = 0;
if(h[a]) p[j] = h[b],h[b] = h[a],h[a] = 0;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n = read(),m = read();
for(int i = 1;i <= n;i ++) siz[c[i] = read()] ++,ans += (c[i] != c[i-1]);
for(int i = 1;i <= n;i ++) {
p[i]=h[c[i]];h[c[i]]=i;
siz[c[i]] ++;
}
for(int i = 1;i <= m;i ++) {
int op = read();
if(op == 2) printf("%d\n",ans);
else {
int x = read(),y = read();
if(x == y) continue;
merge(x,y);
}
}
}
```
该代码可过
by 忘怀星 @ 2021-02-22 18:38:15
map/set 也可以
by myee @ 2021-07-31 17:55:42
@[忘怀星](/user/305911) 已经卡掉了
by cyffff @ 2021-08-26 08:52:58