[文章目录]
Description
就是给你n个数的排名先后，各自为一个集合。然后给出q次操作，每次合并两个集合+查询某一集合排名第k的数的id。
启发式合并splay_tree，每次将小的拆了扔到大的里面。考虑每个节点的合并次数。只有当这个节点在较小的集合中才会被合并。每次所在集合增大至少二倍，所以最多被插入logn次。加上每次插入logn，时间复杂度为O(n*n)。不过据说由于splay因为每次插入都将其旋转到根，大概每次合并的时间复杂度就是siz的，启发式合并splay的时间复杂度就变成了O(nlogn)的。
不过我写的splay。。。一直常数巨大。status里没几个比我慢的。
时间复杂度什么的。。。并没有什么用的。
指针版码力要求感人。
重构三遍得出的经验：
round 1:直接把x所在指针当做根，RE
round 2:每次从x向上一直找到根，中间所有的root都需要重构，细节多，RE
round 3:没有哨兵节点，直接搞，需要特判是否有开区间端点的各种情况，RE
round 4:用一个全局变量now记录当前所在的tree,在rotate的时候直接改变root，使之始终指向根，外加并查集维护splay的根，1A
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,q,fa[101000],now;
char st[200];
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int find(int x){return (x==fa[x])?x:fa[x]=find(fa[x]);}
struct node
{
node *c[2],*fa;
int siz,w,id;
node(int x,int y);
void pushup(){siz=c[0]->siz+c[1]->siz+1;}
}*null=new node(0,0),*root[101000];
void initialize()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
root[i]->c[0]=new node(-1<<30,0);
root[i]->c[1]=new node(1<<30,0);
root[i]->c[0]->fa=root[i];
root[i]->c[1]->fa=root[i];
root[i]->pushup();
}
}
node::node(int x,int y)
{
fa=c[0]=c[1]=null;
siz=null?1:0;
w=x; id=y;
}
void rotate(node *x)
{
node *y=x->fa; bool l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(y==y->fa->c[0]) y->fa->c[0]=x;
else y->fa->c[1]=x;
y->fa=x; y->pushup(); x->pushup();
if(root[now]==y) root[now]=x;
}
void splay(node *x,node *tar)
{
while(x->fa!=tar)
{
node *y=x->fa,*z=y->fa;
if(z==tar){rotate(x); break;}
if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
else rotate(x); rotate(x);
}
}
void insert(node *x)
{
if(x->w==1<<30||x->w==-1<<30) return ;
node *p=root[now],*l,*r; int y=x->w;
while(p!=null)
if(y<p->w) r=p,p=p->c[0];
else l=p,p=p->c[1];
splay(l,null); splay(r,root[now]);
x->siz=1; x->c[0]=x->c[1]=null;
r->c[0]=x; x->fa=r;
r->pushup(); l->pushup();
}
void merge(node *x)
{
if(x==null) return ;
merge(x->c[0]);
node *p=x->c[1];
insert(x);
merge(p);
}
void query(int x,int y)
{
node *p=root[find(x)];
if(y>p->siz-2) puts("-1");
else
{
y++;
while(1)
{
if(y<=p->c[0]->siz) p=p->c[0];
else
{
y-=p->c[0]->siz+1;
if(!y) {printf("%d\n",p->id); return ;}
p=p->c[1];
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) root[i]=new node(read(),i);
initialize();
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
int dx=find(x),dy=find(y);
if(dx!=dy)
{
if(root[dx]->siz>root[dy]->siz) swap(dx,dy);
now=dy;
merge(root[dx]); fa[dx]=dy;
}
}
scanf("%d",&q);
while(q--)
{
scanf("%s%d%d",st,&x,&y);
if(st[0]=='B')
{
int dx=find(x),dy=find(y);
if(dx!=dy)
{
if(root[dx]->siz>root[dy]->siz) swap(dx,dy);
now=dy;
merge(root[dx]); fa[dx]=dy;
}
}
else query(x,y);
}
return 0;
}