【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,特判掉这个错误数据就行啦

上一篇:每天一个linux命令(目录文件操作):【转载】Linux 目录结构


下一篇:Asp.net多行文本框随内容增加而高度增加