[Luogu 3224] HNOI2012 永无乡
<题目链接>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::swap;
const int MAXN=100010,MAXM=400010;
int n,m,q;
class UFS
{
public:
void Init(int i)
{
f[i]=i;
}
int Find(int x)
{
return x==f[x] ? f[x] : f[x]=Find(f[x]);
}
void Merge(int x,int y)
{
f[Find(y)]=Find(x);
}
private:
int f[MAXN];
}S;
class SBT
{
public:
SBT(int cnt=0):cnt(cnt){}
void Init(void)
{
for(int i=1,x;i<=n;++i)
{
scanf("%d",&x);
S.Init(i),s[rt[i]=++cnt]=node(x,i,1);
}
}
void Bridge(int x,int y)
{
int a=S.Find(x),b=S.Find(y);
if(a==b)
return;
if(s[rt[a]].size>s[rt[b]].size)
S.Merge(a,b),Merge(rt[a],b);
else
S.Merge(b,a),Merge(rt[b],a);
}
int FindKth(int x,int k)
{
return k>s[x=rt[S.Find(x)]].size ? -1 : Find(x,k);
}
private:
int cnt,rt[MAXN];
struct node
{
int v,num,size,c[2];
node(int v=0,int num=0,int size=0):v(v),num(num),size(size)
{
memset(c,0,sizeof c);
}
}s[MAXM];
void Update(int i)
{
s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;
}
void Rotate(int &i,bool p)
{
int t=s[i].c[!p];
s[i].c[!p]=s[t].c[p],s[t].c[p]=i;
Update(i),Update(i=t);
}
void Maintain(int &i,bool p)
{
int t=s[s[i].c[!p]].size;
if(t<s[s[s[i].c[p]].c[p]].size)
Rotate(i,!p);
else if(t<s[s[s[i].c[p]].c[!p]].size)
Rotate(s[i].c[p],p),Rotate(i,!p);
else
return;
Maintain(s[i].c[0],0),Maintain(s[i].c[1],1),Maintain(i,0),Maintain(i,1);
}
void Insert(int &i,int x,int num)
{
if(!i)
{
s[i=++cnt]=node(x,num,1);
return;
}
++s[i].size;
bool t=x>s[i].v;
Insert(s[i].c[t],x,num);
Maintain(i,t);
}
void Merge(int &x,int &y)
{
if(!y)
return;
Insert(x,s[y].v,s[y].num),Merge(x,s[y].c[0]),Merge(x,s[y].c[1]);
}
int Find(int i,int x)
{
int t;
while(x!=(t=s[s[i].c[0]].size+1))
if(x<t)
i=s[i].c[0];
else
x-=t,i=s[i].c[1];
return s[i].num;
}
}T;
int main(int argc,char *argv[])
{
scanf("%d %d",&n,&m);
T.Init();
for(int i=1,x,y;i<=m;++i)
{
scanf("%d %d",&x,&y);
T.Bridge(x,y);
}
scanf("%d",&q);
for(int i=1,x,y;i<=q;++i)
{
char c;
scanf("\n%c %d %d",&c,&x,&y);
if(c=='B')
T.Bridge(x,y);
else
printf("%d\n",T.FindKth(x,y));
}
return 0;
}