【BZOJ 2733】【HNOI 2012】永无乡 Splay启发式合并

启发式合并而已啦，，

调试时发现的错误点：insert后没有splay，把要拆开的树的点插入另一个树时没有把ch[2]和fa设为null，找第k大时没有先减k，，，

都是常犯的错误，比赛时再这么粗心就得滚粗了

#include<cstdio>

#include<cstring>

#include<algorithm>

#define read(x) x=getint()

using namespace std;

inline int getint(){char c;int ret=0;for(c=getchar();c<'0'||c>'9';c=getchar());for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';return ret;}

struct node *null;

struct node{

	node();

	node *fa,*ch[2];

	int id,d,s;

	bool pl() {return fa->ch[1]==this;}

	void count() {s=ch[0]->s+ch[1]->s+1;}

	void setc(node *r,bool c) {this->ch[c]=r; if (r!=null) r->fa=this;}

}*rt[100003],pool[100003];

node::node() {d=s=0;ch[0]=ch[1]=fa=null;}

int tot=0,n,m;

inline node *newnode(){

	node *t=&pool[++tot];

	t->ch[0]=t->ch[1]=t->fa=null;

	return t;

}

inline void init() {null=&pool[0];null->s=null->d=0; null->ch[0]=null->ch[1]=null->fa=null;}

inline void rotate(node *r){

	node *f=r->fa; bool c=r->pl();

	if (f->fa!=null) f->fa->setc(r,f->pl());

	else r->fa=null;

	f->setc(r->ch[!c],c); r->setc(f,!c);

	f->count();

}

inline void splay(node *r){

	for(;r->fa!=null;rotate(r))

		if(r->fa->fa!=null)rotate(r->fa->pl()==r->pl()?r->fa:r);

	r->count();

}

inline void ins(node *r,node *k){

	int num=k->d; bool c;

	while (r!=null){

		if (num<r->d) c=0; else c=1;

		if (r->ch[c]==null) {r->setc(k,c); splay(k); return;} else r=r->ch[c];

	}

}

inline node *fdr(node *r) {while (r->fa!=null) r=r->fa; return r;}

inline int QQ(node *r,int k){

	if (r->s<k) return -1;

	while (r!=null){

		if (r->ch[0]->s>=k) r=r->ch[0];

		else if (r->ch[0]->s+1>=k) return r->id;

		else k-=r->ch[0]->s+1,r=r->ch[1];

	}

}

inline void BB(node *r,node *t){

	if (t==null) return;

	BB(r,t->ch[0]); BB(r,t->ch[1]);

	t->ch[0]=t->ch[1]=t->fa=null;

	ins(r,t); splay(t);

}

int main(){

	init();

	read(n); read(m);

	int x,y; char c; node *s,*t;

	for(int i=1;i<=n;++i) {rt[i]=newnode(); read(rt[i]->d); rt[i]->s=1; rt[i]->id=i;}

	for(int i=1;i<=m;++i) {

		read(x); read(y);

		if (x==0||y==0) continue;

		s=fdr(rt[x]); t=fdr(rt[y]);

		if (s==t) continue;

		if (s->s<t->s) swap(s,t);

		BB(s,t);

	}

	read(m);

	while (m--){

		c=getchar();

		while ((c!='Q')&&(c!='B')) c=getchar();

		read(x); read(y);

		switch (c){

			case 'Q':

				printf("%d\n",QQ(fdr(rt[x]),y));

			break;

			case 'B':

				s=fdr(rt[x]); t=fdr(rt[y]);

				if (s==t) continue;

				if (s->s<t->s) swap(s,t);

				if (s!=t) BB(s,t);

			break;

		}

	}

	return 0;

}

PS：最后一组数据有一行是0 0，特判掉这个错误数据就行啦