題目描述：你需要实现\(m\)个操作，操作有两种：
\(1\).把序列中所有值为\(x\)的数的值变成\(y\)。
\(2\).找出一个位置\(i\)满足$ a_{i}=x\(，找出一个位置\)j$满足 \(a_{j}=y\)，使得\(|i-j|\)最小，并输出\(|i-j|\)。
考虑没有\(1\)操作如何维护，我们将每个数的出现次数\(sz_{i}\)分类，若\(sz_{i}>Base\)预处理出这个点到每个颜色的最短路径，将其存到\(ans\)数组，否则询问时暴力归并得到答案，通常我们令\(Base=\sqrt{n}\)。
加入\(1\)操作我们也会想用一种类似的方法维护，但加入修改后我们需要对\(ans\)数组进行重构，对此，我们展开以下讨论(在讨论中，我们默认\(sz_{x}<sz_{y}\),可以用启发式合并转置的思想来\(swap(x,y)\)，并默认\(n,q\)同阶)。
\(1.\)当\(sz_{x}<=Base,sz_{y}<=Base\)，可以直接暴力归并，如果归并后\(sz_{x}>Base\)的话进行重构，每一次归并的复杂度为\(O(Base)\),重构的次数为\(O(\frac{n}{Base})\),复杂度\(O(n\times (Base+\frac{n}{Base}))\)。
\(2.\)当\(sz_{x}>Base,sz_{y}>Base\)，归并的次数仅有\(O(\frac{n}{Base})\)次，暴力归并，暴力重构即可。
\(3.\)当\(sz_{x}<=Base,sz_{y}>Base\)，直接归并重构复杂度都不对，我们可以借用懒标记的思想，对每一个\(sz>Base\)的维护一个附属集合，然后将\(x\)加入\(y\)的附属集合，若附属集合\(sz>Base\)则重构\(ans\)数组。事实上，它是\(1,2\)的平衡。
在查询的时候：
\(1.\)当\(sz_{x}<=Base,sz_{y}<=Base\)，暴力归并即可。
\(2.\)当\(sz_{x}>Base,sz_{y}>Base\)，将\(ans\)与附属集合归并的结果取\(min\)即可。
\(3.\)当\(sz_{x}<=Base,sz_{y}>Base\)，将\(ans\)与\(y\)的附属集合与\(x\)归并的结果取\(min\)即可。
当\(Base=\sqrt{n}\)时取到最优复杂度为\(O(n\sqrt{n})\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define N 100000
#define B 350
#define inf 1000000000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,Base,a[N+1],sz[N+1],res[B+1][N+1],length,p[N+1],ans,lstans,color[N+1];
vector<int>P[N+1];
vector<int>T;
int rt[N+1];
void solve(int x)
{
int lst=-inf;
for (int i=1;i<=N;++i) res[p[x]][i]=inf;
for (int i=1;i<=n;++i)
{
if (a[i]==x) lst=i;
else res[p[x]][a[i]]=min(res[p[x]][a[i]],i-lst);
}
lst=inf;
for (int i=n;i>=1;--i)
{
if (a[i]==x) lst=i;
else res[p[x]][a[i]]=min(res[p[x]][a[i]],lst-i);
}
return;
}
int merge(int x,int y)
{
int res=inf,pv=-1;
for (int i=0;i<P[y].size();++i)
{
while (pv!=(int)(P[x].size())-1&&P[x][pv+1]<=P[y][i]) pv++;
if (pv!=-1) res=min(res,P[y][i]-P[x][pv]);
}
pv=P[x].size();
for (int i=(int)(P[y].size())-1;i>=0;--i)
{
while (pv!=0&&P[x][pv-1]>=P[y][i]) pv--;
if (pv!=P[x].size()) res=min(res,P[x][pv]-P[y][i]);
}
return res;
}
void solve_merge(int x,int y)
{
T.clear();
int pv=-1;
for (int i=0;i<P[y].size();++i)
{
while (pv!=(int)(P[x].size())-1&&P[x][pv+1]<=P[y][i]) T.push_back(P[x][++pv]);
T.push_back(P[y][i]);
}
for (int i=pv+1;i<P[x].size();++i) T.push_back(P[x][i]);
swap(T,P[y]),P[x].clear();
return;
}
void changer(int x,int y)
{
if (x==y) return;
int tx=color[x],ty=color[y];
if (sz[tx]>sz[ty]) swap(tx,ty),swap(color[x],color[y]),swap(x,y);
for (int i=1;i<=length;++i) res[i][ty]=min(res[i][ty],res[i][tx]),res[i][tx]=inf;
if (sz[tx]>Base&&sz[ty]>Base)
{
for (int i=1;i<=n;++i)
if (a[i]==tx)
a[i]=ty;
P[tx].clear(),P[ty].clear(),solve(ty);
}
else if (sz[tx]<=Base&&sz[ty]>Base)
{
for (int i=0;i<P[tx].size();++i) a[P[tx][i]]=ty;
solve_merge(tx,ty);
if (P[ty].size()>Base) P[ty].clear(),solve(ty);
}
else if (sz[tx]<=Base&&sz[ty]<=Base)
{
for (int i=0;i<P[tx].size();++i) a[P[tx][i]]=ty;
solve_merge(tx,ty);
if (P[ty].size()>Base) P[ty].clear(),p[ty]=++length,solve(ty);
}
sz[ty]+=sz[tx],sz[tx]=0;
return;
}
void query(int x,int y)
{
x=color[x],y=color[y];
if (sz[x]==0||sz[y]==0)
{
lstans=0;
puts("Ikaros");
return;
}
if (x==y)
{
lstans=0;
puts("0");
return;
}
if (sz[x]>sz[y]) swap(x,y);
if (sz[x]>Base&&sz[y]>Base) printf("%d\n",lstans=min(min(res[p[x]][y],res[p[y]][x]),merge(x,y)));
else if (sz[x]<=Base&&sz[y]>Base) printf("%d\n",lstans=min(res[p[y]][x],merge(x,y)));
else printf("%d\n",lstans=merge(x,y));
return;
}
int main()
{
int op,x,y;
n=read(),m=read(),Base=sqrt(n);
for (int i=1;i<=n;++i) a[i]=read(),sz[a[i]]++;
for (int i=1;i<=N;++i) rt[i]=i,color[i]=i;
for (int i=1;i<=n;++i)
if (sz[a[i]]<=Base)
P[a[i]].push_back(i);
for (int i=1;i<=N;++i)
if (sz[i]>Base)
p[i]=++length,solve(i);
lstans=0;
for (int i=1;i<=m;++i)
{
op=read(),x=read(),y=read(),x^=lstans,y^=lstans;
if (op==1) changer(x,y);
else query(x,y);
}
return 0;
}