典型Splay练习题。
开始建 \(n\) 个Splay，每一次建边用并查集判断是否在一个子图，不在就合并，即把一个Splay的所有点全插入到另一个Splay中，需要合并的点可以用vector存储。
但这样复杂度极限为 \(O(n^2\times \log(n))\)，会T，所以要借助启发式合并。
证明启发式合并复杂度：
对于每一次合并，当 \(len_i=len_j\) 时合并时间复杂度越大，所以易证，对于每一个从 \(len_i=1\) 开始的Splay树，只需进行 \(\log(n)\) 次即可将合并规模达到 \(n\)。
所以启发式合并后的复杂度为 \(O(n\times\log^2(n))\)
附代码：
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+5;
vector<int>a[N];
struct node
{
int fa,ch[2],val,siz,cnt;
}t[N];
int n,cnt,root[N],p[N],m,f[N];
void newnode(int &x,int val,int fa)
{
x=++cnt;
t[x].fa=fa;
t[x].val=val;
t[x].cnt=t[x].siz=1;
}
void connect(int x,int fa,int son)
{
t[x].fa=fa;
t[fa].ch[son]=x;
}
bool ident(int x,int fa)
{
return t[fa].ch[1]==x;
}
void pushup(int x)
{
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}
void rotate(int x)
{
int fa=t[x].fa,ff=t[fa].fa,k=ident(x,fa);
connect(t[x].ch[k^1],fa,k);
connect(fa,x,k^1);
connect(x,ff,ident(fa,ff));
pushup(fa),pushup(x);
}
void Splay(int x,int p=0,int topp=0)
{
if(!topp)root[p]=x;
while(t[x].fa!=topp)
{
int fa=t[x].fa,ff=t[fa].fa;
if(ff!=topp)ident(x,fa)^ident(fa,ff)?rotate(x):rotate(fa);
rotate(x);
}
}
void insert(int val,int &x,int num,int id=0,int to=0,int fa=0)
{
if(!x&&!id)newnode(x,val,fa),Splay(x,num);
else if(!x&&id)x=id,t[x].ch[0]=t[x].ch[1]=0,connect(id,fa,to),Splay(id,num);
else if(t[x].val>val)insert(val,t[x].ch[0],num,id,0,x);
else if(t[x].val<val)insert(val,t[x].ch[1],num,id,1,x);
else t[x].cnt++,Splay(x,num);
}
int getval(int k,int x,int num)
{
if(!x)return -1;
if(k<=0)
{
Splay(x,num);
return x;
}
if(k<=t[t[x].ch[0]].siz)return getval(k,t[x].ch[0],num);
int tmp=k-t[t[x].ch[0]].siz-t[x].cnt;
if(tmp<=0)
{
Splay(x,num);
return x;
}
else return getval(tmp,t[x].ch[1],num);
}
int afind(int x)
{
if(f[x]==x)return x;
return f[x]=afind(f[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
f[i]=i;
a[i].push_back(i);
insert(p[i],root[i],i);
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(afind(u)!=afind(v))
{
int k=afind(v),kt=afind(u);
if(a[k].size()>a[kt].size())swap(k,kt);
int len=a[k].size();
for(int j=0;j<len;j++)
{
a[kt].push_back(a[k][j]);
insert(p[a[k][j]],root[kt],kt,a[k][j]);
}
f[k]=kt;
}
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
char opt;
scanf("%c",&opt);
while(opt!='B'&&opt!='Q')scanf("%c",&opt);
int x,y;
scanf("%d%d",&x,&y);
if(opt=='B')
{
if(afind(x)!=afind(y))
{
int k=afind(y),kt=afind(x);
if(a[k].size()>a[kt].size())swap(k,kt);
int len=a[k].size();
for(int j=0;j<len;j++)
{
a[kt].push_back(a[k][j]);
insert(p[a[k][j]],root[kt],kt,a[k][j]);
}
f[k]=kt;
}
}
if(opt=='Q')
{
int k=afind(x);
int ans=getval(y,root[k],k);
printf("%d\n",ans);
}
}
return 0;
}