学步园

SBT神器啊，川大校赛出了个基本的SBT，他们搞的数据有点恶心，写了好几次都没过掉

http://222.196.33.254/oj/showproblem?problem_id=1716
这个是我们学院上的地址，不过好像只有教育网可以登

感觉SBT就是size一个信息就可以解决n多动态查询问题了

这个可以用来当做模板，自己写的代码可读性还是比较高

/*<br /> * File: main.cpp<br /> * Author: Mi<br /> *<br /> * Created on 2011年4月13日, 下午7:51<br /> */<br /> #include <cstdlib><br /> #include <stdio.h><br /> #include <string.h><br /> #include <algorithm><br /> #include <cassert><br /> #define N 500005<br /> using namespace std;<br /> /*<br /> *<br /> */<br /> int tol=0;<br /> struct SBT<br /> {<br /> int left,right;<br /> int key;<br /> int size;<br /> void init()<br /> {<br /> left=right=0;<br /> size=1;<br /> }<br /> }T[N];<br /> void R_Rotate(int &t)//右旋<br /> {<br /> int k=T[t].left;<br /> T[t].left=T[k].right;<br /> T[k].right=t;<br /> T[k].size=T[t].size;<br /> T[t].size=T[T[t].left].size+T[T[t].right].size+1;<br /> t=k;<br /> return ;<br /> }<br /> void L_Rotate(int &t)//左旋<br /> {<br /> int k=T[t].right;<br /> T[t].right=T[k].left;<br /> T[k].left=t;<br /> T[k].size=T[t].size;<br /> T[t].size=T[T[t].left].size+T[T[t].right].size+1;<br /> t=k;<br /> }<br /> void Maintain(int &t,bool flag)//维护，SBT精华之所在<br /> {<br /> if(flag==false)<br /> {<br /> if(T[T[T[t].left].left].size>T[T[t].right].size)<br /> R_Rotate(t);<br /> else if(T[T[T[t].left].right].size>T[T[t].right].size)<br /> {<br /> L_Rotate(T[t].left);<br /> R_Rotate(t);<br /> }<br /> else<br /> return ;<br /> }<br /> else<br /> {<br /> if(T[T[T[t].right].right].size>T[T[t].left].size)<br /> L_Rotate(t);<br /> else if(T[T[T[t].right].left].size>T[T[t].left].size)<br /> {<br /> R_Rotate(T[t].right);<br /> L_Rotate(t);<br /> }<br /> else<br /> return ;<br /> }<br /> Maintain(T[t].left,false);<br /> Maintain(T[t].right,true);<br /> Maintain(t,false);<br /> Maintain(t,true);<br /> }<br /> void Insert(int &t,int v)//插入<br /> {<br /> if(t==0)<br /> {<br /> t=++tol;<br /> T[t].init();<br /> T[t].key=v;<br /> }<br /> else<br /> {<br /> T[t].size++;<br /> if(v<T[t].key)<br /> Insert(T[t].left,v);<br /> else<br /> Insert(T[t].right,v);<br /> Maintain(t,v>=T[t].key);<br /> }<br /> }<br /> int Delete(int &t,int v)//删除<br /> {<br /> if(!t)<br /> return 0;<br /> T[t].size--;<br /> if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)<br /> {<br /> if(T[t].left&&T[t].right)<br /> {<br /> int p=Delete(T[t].left,v+1);<br /> T[t].key=T[p].key;<br /> return p;<br /> }<br /> else<br /> {<br /> int p=t;<br /> t=T[t].left+T[t].right;<br /> return p;<br /> }<br /> }<br /> else<br /> return Delete(v<T[t].key?T[t].left:T[t].right,v);<br /> }<br /> int Find_k(int t,int k)//找出第k大数<br /> {<br /> if(k<=T[T[t].left].size)<br /> return Find_k(T[t].left,k);<br /> else if(k>T[T[t].left].size+1)<br /> return Find_k(T[t].right,k-T[T[t].left].size-1);<br /> return T[t].key;<br /> }<br /> int Getmin(int t)//取最小值<br /> {<br /> while(T[t].left)<br /> t=T[t].left;<br /> return t;<br /> }<br /> int Getmax(int t)//取最大值<br /> {<br /> while(T[t].right)<br /> t=T[t].right;<br /> return t;<br /> }<br /> int Rank(int t,int key)//排名其实就是它的左子树的size+1<br /> {<br /> if(t==0)<br /> return 0;<br /> if(key<=T[t].key)<br /> return Rank(T[t].left,key);<br /> else<br /> return T[T[t].left].size+1+Rank(T[t].right,key);<br /> }<br /> int Exist(int t,int x)//判断这个节点是否存在<br /> {<br /> if(t==0)<br /> return 0;<br /> if(x<T[t].key)<br /> return Exist(T[t].left,x);<br /> else if(x==T[t].key)<br /> return 1;<br /> else<br /> return Exist(T[t].right,x);<br /> }<br /> int Count(int t,int x)//统计出现次数<br /> {<br /> if(!Exist(t,x))<br /> return 0;<br /> else<br /> return Rank(t,x+1)-Rank(t,x);<br /> }<br /> int Pred(int t,int v)//返回比v小的最大的数<br /> {<br /> if(t==0)<br /> return v;<br /> else if(v>T[t].key)<br /> {<br /> int ret=Pred(T[t].right,v);<br /> if(ret==v)<br /> return T[t].key;<br /> return ret;<br /> }<br /> else<br /> return Pred(T[t].left,v);<br /> }<br /> int Succ(int t,int v)//返回比v大的最小的数<br /> {<br /> if(t==0)<br /> return v;<br /> else if(v<T[t].key)<br /> {<br /> int ret=Succ(T[t].left,v);<br /> if(ret==v)<br /> return T[t].key;<br /> return ret;<br /> }<br /> else<br /> return Succ(T[t].right,v);<br /> }<br /> int main(int argc, char** argv)<br /> {<br /> int t,q;<br /> // freopen("j1.in","r",stdin);<br /> // freopen("out.out","w",stdout);<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> int root=0;<br /> tol=0;<br /> scanf("%d",&q);<br /> while(q--)<br /> {<br /> char str[5];<br /> int x;<br /> scanf("%s",str);<br /> if(str[0]=='I')<br /> {<br /> scanf("%d",&x);<br /> Insert(root,x);<br /> }<br /> else if(str[0]=='R')<br /> {<br /> scanf("%d",&x);<br /> if(Exist(root,x))<br /> Delete(root,x);<br /> }<br /> else if(str[0]=='S')<br /> printf("%d/n",T[root].size);<br /> else if(str[0]=='L')<br /> {<br /> scanf("%d",&x);<br /> printf("%d/n",Rank(root,x));<br /> }<br /> else if(str[0]=='W')<br /> {<br /> scanf("%d",&x);<br /> if(x<1||x>T[root].size)<br /> printf("-1/n");<br /> else<br /> printf("%d/n",Find_k(root,x));<br /> }<br /> else if(str[0]=='C')<br /> {<br /> scanf("%d",&x);<br /> printf("%d/n",Count(root,x));<br /> }<br /> else if(str[1]=='I')<br /> {<br /> if(root==0)<br /> puts("-1");<br /> else<br /> printf("%d/n",T[Getmin(root)].key);<br /> }<br /> else if(str[1]=='A')<br /> {<br /> if(root==0)<br /> puts("-1");<br /> else<br /> printf("%d/n",T[Getmax(root)].key);<br /> }<br /> /* else if(str[0]=='P')<br /> {<br /> scanf("%d",&x);<br /> printf("%d/n",Pred(root,x));<br /> }<br /> else if(str[1]=='U')<br /> {<br /> scanf("%d",&x);<br /> printf("%d/n",Succ(root,x));<br /> }*/<br /> }<br /> }<br /> return 0;<br /> }