这个代码翻译过来就是，有$n$个数，每个数有一种颜色，$m$次操作把颜色$x$替换成$y$，求每次替换后同种颜色最近点对。

然后这个替换颜色就是很板的启发式合并。

考虑统计答案，发现答案不增，所以每次启发式合并插入的时候计算答案，和原来的答案取$min$即可。

用$set$可以做到$O(log{n})$单次，启发式合并$O(nlogn)$，总复杂度$O(n log^2 {n})$>

不用启发式合并看起来有$\geq 90pts$，数据水成啥了..

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n,m;
int a[101000];
int X[101000],Y[101000];
int b[301000],btt;
int EF(int x){
	int l=1,r=btt;
	while(l<r){
		int mid=((l+r)>>1);
		if(b[mid]>=x) r=mid;
		else l=mid+1;
	}return l;
}
int lst[301000];
int col[301000],fcol[301000];
int sz[301000];
set<int>setz[301000],setf[301000];
int st[301000],top;
signed main(){
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc my.out ex.out");return 0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[++btt]=a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>X[i]>>Y[i];
		b[++btt]=X[i];b[++btt]=Y[i]; 
	}
	sort(b+1,b+btt+1);
	btt=unique(b+1,b+btt+1)-b-1;
	int ans=2147483647;
	for(int i=1;i<=n;i++){
		a[i]=EF(a[i]);
		if(lst[a[i]]) ans=min(ans,i-lst[a[i]]);
		lst[a[i]]=i;
		sz[a[i]]++;
		setz[a[i]].insert(i);
		setf[a[i]].insert(-i);
	}
	for(int i=1;i<=btt;i++) col[i]=fcol[i]=i;
	for(int i=1;i<=m;i++){
		X[i]=EF(X[i]);
		Y[i]=EF(Y[i]);
		int cx=fcol[X[i]],cy=fcol[Y[i]];
		if(sz[cx]>sz[cy]){
			swap(fcol[X[i]],fcol[Y[i]]);
			swap(col[cx],col[cy]);
			swap(cx,cy);
		}
		if(cx==cy){
			cout<<ans<<"\n";
			continue;
		} 
		sz[cy]+=sz[cx];sz[cx]=0;
		for(auto x:setz[cx]){
			if(setz[cy].lower_bound(x)!=setz[cy].end()){
				ans=min(ans,abs(*setz[cy].lower_bound(x)-x));
			} 
			if(setf[cy].lower_bound(-x)!=setf[cy].end()){
				ans=min(ans,abs(*setf[cy].lower_bound(-x)+x));
			} 
			setz[cy].insert(x);
			setf[cy].insert(-x);
			st[++top]=x;
		}
		while(top){
			setz[cx].erase(st[top]);
			setf[cx].erase(-st[top]);
			top--;
		}
		cout<<ans<<"\n";
	}
	return 0;
} 

切入点在于我们要维护的答案：同种颜色最近距离，不涉及颜色修改显然可以对每种颜色线性枚举统计答案。我们把整个修改拆解成单个插入。为了统计是否造成贡献就需要找到插入的下标在他插入的集合里的前驱和后继，显然可以平衡树（set实现）。

考虑到我最开始想到的是块状链表维护插入，还是太魔怔了（传奇$O(nlogn\sqrt{n})$做法）。

至于插入颜色的方法显然应该启发式合并，因为只有合并没有分裂，怎么会有人写线段树合并呢？

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


map<int, set<int>>mp;
int ans = 2147483647;
void dis(int id, int x){  // 更新答案
    auto it = mp[id].lower_bound(x);
    if(it != mp[id].end()) ans = min(ans, *it - x);
    if(it != mp[id].begin()) --it, ans = min(ans, x - *it);
}
void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1 ; i <= n ; i ++) {
        int x; scanf("%d", &x);
        dis(x, i);
        mp[x].insert(i);
    }
    while(m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y) printf("%d\n", ans);
        else {
            if (mp[x].size() > mp[y].size()) swap(mp[x], mp[y]);
            for (auto it : mp[x]) {  // 启发式合并, 小的往大的上面并
                dis(y, it);
                mp[y].insert(it);
            }
            mp[x].clear(); printf("%d\n", ans);
        }
    }
}
int main()
{
    solve();
    return 0;
}