C++(g++ 7.5.0) 解法, 执行用时: 91ms, 内存消耗: 27792K, 提交时间: 2023-03-30 13:18:43

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

int n, m;
int a[N];
vector<int> pos[N];
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]].push_back(i);
	}
	
	for (int i = 1; i <= n + 1; i++) {
		ans += a[i] != a[i - 1];
	}
	
	while (m--) {
		int op, x, y;
		cin >> op;
		
		if (op == 1) {
			cin >> x >> y;
			if (x == y) continue;
			
			if (pos[x].size() > pos[y].size()) {
				pos[x].swap(pos[y]);
			}
			
			if (pos[y].size() == 0) continue;
			int col = a[pos[y][0]];
			
			for (int j = 0; j < pos[x].size(); j++) {
				int i = pos[x][j];
				pos[y].push_back(i);
				ans -= (a[i] != a[i - 1]) + (a[i] != a[i + 1]);
				a[i] = col;
				ans += (a[i] != a[i - 1]) + (a[i] != a[i + 1]);
			}
			
			pos[x].clear();
		} else {
			cout << ans - 1 << "\n";
		}
	}
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 138ms, 内存消耗: 31200K, 提交时间: 2019-07-10 16:21:31

#include<bits/stdc++.h>
using namespace std;
int ans=0;
const int maxn=1e6+10;
int c[maxn];int y[maxn]; 
vector <int> p[1000008];
void fun(int x,int y){
	for(int i=p[x].size()-1;i>=0;i--){
		ans-=(c[p[x][i]-1]==y)+(c[p[x][i]+1]==y);
		
	}
	for(int i=p[x].size()-1;i>=0;i--)
	{
		c[p[x][i]]=y;p[y].push_back(p[x][i]);
	}
	p[x].clear();
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		y[c[i]]=c[i];
		p[c[i]].push_back(i);
		if(c[i]!=c[i-1])	ans++;
	}
	int t1,t2,t3;
	while(m--)
	{
		scanf("%d",&t1);
		if(t1==2)	printf("%d\n",ans);
		else{
			scanf("%d%d",&t2,&t3);
			if(t2==t3)	continue;
			if(p[y[t2]].size()>p[y[t3]].size())	swap(y[t2],y[t3]);
			if(p[y[t2]].size())	fun(y[t2],y[t3]);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 102ms, 内存消耗: 8924K, 提交时间: 2020-04-12 15:45:09

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,ans,b[N],a[N],c[N],p[N],h[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	b[a[i]]=a[i],c[a[i]]++;
    	p[i]=h[a[i]],h[a[i]]=i;
    	if(a[i]!=a[i-1])ans++;
	}
    for(int i=1;i<=m;i++){
    	int f,x,y;
		scanf("%d",&f);
		if(f==1){
			scanf("%d%d",&x,&y);
			if(x==y)continue;
			if(c[b[x]]>c[b[y]])swap(b[x],b[y]);
			x=b[x],y=b[y];
			for(int j=h[x];j;j=p[j]){
				if(a[j+1]==y)ans--;
				if(a[j-1]==y)ans--;
			}
			int k;
			for(int j=h[x];j;j=p[j])a[j]=y,k=j;
			if(h[x])p[k]=h[y],h[y]=h[x];
			c[y]+=c[x],h[x]=c[x]=0;
		}
		else{
			printf("%d\n",ans);
		}
	}
    return 0;
}