昨天晚上wq学长讲课，讲完让人略微懵逼的KD-tree，学长心血来潮要讲替罪羊树
学长：尽管这个玩意又臭又长，但是我从学会一直打到了退役，你们今天晚上和明天上午可以不看板子自己YY一下
一向乖巧听话（人怂胆小）的我觉得学长说得对啊，然后第二天早上我欣然开始了替罪羊树之旅，并不知道后面等着我的是什么
刚开始非常顺利得码完，和ce抗衡取得成功，然后输入样例，RE
然后发现插入时没处理根，改了之后成功通过样例，提交，WA10，经测验发现数据有样例。。。。。。
高兴（？）地调啊调啊调，终于得到了40分的好成绩，然后经过和随机数据生成的艰苦斗争，终于发现前趋后继死活查不对
中午和*****一起******，开心
下午上网查发现这个玩意没有很好的查前趋方法，最优(bao)美(li)的只有
我@#%$@#$#^#$@#$%@#
码完成功AC
替罪羊树，听上去好像很高大上，但研究后发现替罪羊树的核心是看似极度暴力的操作：重建
一棵BST，在连续插入递增权值时可能退化成一条链，之前我们都是通过旋转等操作使之始终保持平衡，
这里我们换一个思路，每次插入&删除后进行检查，发现不平衡直接重建整个子树
很容易发现我们每次要尽量在靠上的节点为根开始重建
又由于每次插入以及删除只对一条链有影响，扫这条链就好了
#include<bits/stdc++.h> using namespace std; inline int read(){ int a=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+ch-'0',ch=getchar(); return a*f; } struct node{ node *ch[2],*f; int cnt,rs,val,size,del,fal; }*rt=NULL,pool[1000100]; int tot,que[500100],top,qus[500100]; inline node* New(const int val){ ++tot; pool[tot].ch[0]=pool[tot].ch[1]=pool[tot].f=NULL; pool[tot].cnt=pool[tot].size=pool[tot].rs=1; pool[tot].del=pool[tot].fal=0; pool[tot].val=val; return &pool[tot]; } inline void up(node *x){ for(;x!=NULL;x=x->f){ x->size=x->cnt; x->rs=1; x->fal=x->del; if(x->ch[0]!=NULL) x->size+=x->ch[0]->size,x->rs+=x->ch[0]->rs,x->fal+=x->ch[0]->fal; if(x->ch[1]!=NULL) x->size+=x->ch[1]->size,x->rs+=x->ch[1]->rs,x->fal+=x->ch[1]->fal; } } const double arf=0.75,re=0.3; inline void dfs(node *x){ if(x==NULL) return; dfs(x->ch[0]); if(!x->del) que[++top]=x->val,qus[top]=x->cnt; dfs(x->ch[1]); x=NULL; } void chs(const int l,const int r,node *&now,node *fa){ if(l>r) return; int mid=(l+r>>1); now=New(que[mid]); now->cnt=qus[mid]; now->f=fa; chs(l,mid-1,now->ch[0],now); chs(mid+1,r,now->ch[1],now); if(now->ch[0]==NULL&&now->ch[1]==NULL)up(now); } inline void change(node *x,node *fa){ top=0; dfs(x); if(fa==NULL){ chs(1,top,rt,NULL); return; } bool t=fa->ch[1]==x; chs(1,top,fa->ch[t],fa); } inline void check(const int val){ if(rt->fal>arf*rt->rs+3){ change(rt,NULL); return; } for(node *now=rt,*fa=NULL;now!=NULL&&now->val!=val;fa=now,now=now->ch[val>now->val]) if(now!=rt){ if(now->ch[0]!=NULL&&now->ch[0]->rs>=arf*now->rs+3){ change(now,fa); return; } if((now->ch[1]!=NULL&&now->ch[1]->rs>=arf*now->rs+3)){ change(now,fa); return; } } } inline void insert(const int val){ if(rt==NULL){ rt=New(val); return; } for(node *now=rt,*fa=NULL;;fa=now,now=now->ch[val>now->val]){ if(now==NULL){ fa->ch[val>fa->val]=now=New(val); now->f=fa; up(now); check(val); return; } if(val==now->val){ if(now->del) now->del=0; now->cnt++; up(now); return; } } } inline int rnk(const int val){ int ans=0; for(node *now=rt;now!=NULL;) if(val<now->val) now=now->ch[0]; else { if(now->ch[0]!=NULL) ans+=now->ch[0]->size; if(now->val==val) return ans+1; ans+=now->cnt; now=now->ch[1]; } } inline node* kth(int k){ for(node *now=rt;now!=NULL;) if(now->ch[0]!=NULL&&k<=now->ch[0]->size) now=now->ch[0]; else{ int tmp=now->cnt; if(now->ch[0]!=NULL) tmp+=now->ch[0]->size; if(tmp>=k) return now; k-=tmp; now=now->ch[1]; } } inline void dlt(const int val){ for(node *now=rt;now!=NULL;now=now->ch[val>now->val]) if(now->val==val){ now->cnt--; if(!now->cnt) now->del=1; up(now); check(val); return; } } int main(){ int n,x,y; n=read(); for(int i=1;i<=n;i++){ x=read();y=read(); switch(x){ case 1:insert(y); break; case 2:dlt(y); break; case 3:printf("%d ",rnk(y)); break; case 4:printf("%d ",kth(y)->val); break; case 5:insert(y); printf("%d ",kth(rnk(y)-1)->val); dlt(y); break; case 6:insert(y+1); x=rnk(y+1); dlt(y+1); printf("%d ",kth(x)->val); break; } } }