首页 > 代码库 > Tyvj 1730 论我们有多少种方法调戏普通平衡树（其实是备忘录）
Tyvj 1730 论我们有多少种方法调戏普通平衡树（其实是备忘录）
题面不用贴了，做过的都知道……
数组Treap
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 struct node{ 6 int l,r,v,size,rnd,w; 7 }tr[100005]; 8 int n,size,root,ans; 9 void Update(int k) 10 { 11 tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w; 12 } 13 void Zig(int &k)//右旋 14 { 15 int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k; 16 tr[t].size=tr[k].size;Update(k);k=t; 17 } 18 void Zag(int &k)//左旋 19 { 20 int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k; 21 tr[t].size=tr[k].size;Update(k);k=t; 22 } 23 void Insert(int &k,int x) 24 { 25 if(!k) 26 { 27 size++;k=size; 28 tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand(); 29 return; 30 } 31 tr[k].size++; 32 if(tr[k].v==x)tr[k].w++; 33 else if(x>tr[k].v) 34 { 35 Insert(tr[k].r,x); 36 if(tr[tr[k].r].rnd<tr[k].rnd)Zag(k); 37 } 38 else 39 { 40 Insert(tr[k].l,x); 41 if(tr[tr[k].l].rnd<tr[k].rnd)Zig(k); 42 } 43 } 44 void Del(int &k,int x) 45 { 46 if(!k)return; 47 if(tr[k].v==x) 48 { 49 if(tr[k].w>1) 50 { 51 tr[k].w--;tr[k].size--;return; 52 } 53 if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r; 54 else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) 55 { 56 Zig(k); 57 Del(k,x); 58 } 59 else 60 { 61 Zag(k); 62 Del(k,x); 63 } 64 } 65 else if(x>tr[k].v) 66 { 67 tr[k].size--; 68 Del(tr[k].r,x); 69 } 70 else 71 { 72 tr[k].size--; 73 Del(tr[k].l,x); 74 } 75 } 76 int Query_Rank(int k,int x) 77 { 78 if(!k)return 0; 79 if(tr[k].v==x)return tr[tr[k].l].size+1; 80 else if(x>tr[k].v) 81 return tr[tr[k].l].size+tr[k].w+Query_Rank(tr[k].r,x); 82 else return Query_Rank(tr[k].l,x); 83 } 84 int Query_Num(int k,int x) 85 { 86 if(!k)return 0; 87 if(x<=tr[tr[k].l].size)return Query_Num(tr[k].l,x); 88 else if(x>tr[tr[k].l].size+tr[k].w) 89 return Query_Num(tr[k].r,x-tr[tr[k].l].size-tr[k].w); 90 else return tr[k].v; 91 } 92 void Query_Pro(int k,int x) 93 { 94 if(!k)return; 95 if(tr[k].v<x) 96 { 97 ans=k; 98 Query_Pro(tr[k].r,x); 99 } 100 else Query_Pro(tr[k].l,x); 101 } 102 void Query_Sub(int k,int x) 103 { 104 if(!k)return; 105 if(tr[k].v>x) 106 { 107 ans=k; 108 Query_Sub(tr[k].l,x); 109 } 110 else Query_Sub(tr[k].r,x); 111 } 112 int haha() 113 { 114 freopen("phs.in","r",stdin); 115 freopen("phs.out","w",stdout); 116 scanf("%d",&n); 117 int opt,x; 118 for(int i=1;i<=n;i++) 119 { 120 scanf("%d%d",&opt,&x); 121 switch(opt) 122 { 123 case 1:Insert(root,x);break; 124 case 2:Del(root,x);break; 125 case 3:printf("%d\n",Query_Rank(root,x));break; 126 case 4:printf("%d\n",Query_Num(root,x));break; 127 case 5:ans=0;Query_Pro(root,x);printf("%d\n",tr[ans].v);break; 128 case 6:ans=0;Query_Sub(root,x);printf("%d\n",tr[ans].v);break; 129 } 130 } 131 //while(1); 132 } 133 int MsZhangMingtao=haha(); 134 int main(){;}
指针Treap
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using namespace std; 6 #define ls(x) (x->ch[0]) 7 #define rs(x) (x->ch[1]) 8 #define size(x) ((x)?(x->size):(0)) 9 struct Treap 10 { 11 int size,key,v; 12 Treap *ch[2]; 13 Treap(int x=0) 14 { 15 v=x; 16 size=1; 17 key=rand(); 18 ch[0]=ch[1]=NULL; 19 } 20 }*root; 21 void Maintain(Treap *rt) 22 { 23 rt->size=size(ls(rt))+size(rs(rt))+1; 24 } 25 void Rotate(Treap* &rt,int d) 26 { 27 Treap *t=rt->ch[d^1]; 28 rt->ch[d^1]=t->ch[d];Maintain(rt); 29 t->ch[d]=rt;Maintain(t); 30 rt=t; 31 } 32 void Insert(Treap* &rt,int x) 33 { 34 if(!rt) 35 { 36 rt=new Treap(x); 37 return; 38 } 39 int d=rt->v>x; 40 Insert(rt->ch[d^1],x); 41 Maintain(rt); 42 if(rt->ch[d^1]->key>rt->key)Rotate(rt,d); 43 } 44 void Delete(Treap* &rt,int x) 45 { 46 if(rt->v==x) 47 { 48 if(ls(rt)&&rs(rt)) 49 { 50 int d=ls(rt)->key>rs(rt)->key; 51 Rotate(rt,d); 52 Delete(rt->ch[d],x); 53 } 54 else 55 { 56 Treap *t=NULL; 57 if(ls(rt))t=ls(rt); 58 else t=rs(rt); 59 delete rt;rt=t; 60 } 61 } 62 else 63 { 64 int d=rt->v>x; 65 Delete(rt->ch[d^1],x); 66 } 67 if(rt)Maintain(rt); 68 } 69 int Rank(int x) 70 { 71 Treap *rt=root; 72 int res=0; 73 while(rt) 74 { 75 if(x>rt->v) 76 { 77 res+=size(ls(rt))+1; 78 rt=rs(rt); 79 } 80 else rt=ls(rt); 81 } 82 return res; 83 } 84 int Kth(int k) 85 { 86 Treap *rt=root; 87 while(rt) 88 { 89 if(size(ls(rt))+1==k)return rt->v; 90 if(size(ls(rt))+1>k)rt=ls(rt); 91 else 92 { 93 k-=size(ls(rt))+1; 94 rt=rs(rt); 95 } 96 } 97 return 0; 98 } 99 int haha() 100 { 101 freopen("phs.in","r",stdin); 102 freopen("phs.out","w",stdout); 103 int n;scanf("%d",&n); 104 while(n--) 105 { 106 int opt,x;scanf("%d%d",&opt,&x); 107 switch(opt) 108 { 109 case 1:Insert(root,x);break; 110 case 2:Delete(root,x);break; 111 case 3:printf("%d\n",Rank(x)+1);break; 112 case 4:printf("%d\n",Kth(x));break; 113 case 5:printf("%d\n",Kth(Rank(x)));break; 114 case 6:printf("%d\n",Kth(Rank(x+1)+1));break; 115 } 116 } 117 //while(1); 118 } 119 int WormYuZhuohao=haha(); 120 int main(){;}
Splay
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define ls(x) (x->ch[0]) 7 #define rs(x) (x->ch[1]) 8 #define fa(x) (x->pa) 9 #define size(x) ((x) ? (x->size) : (0)) 10 const int INF=2000000000; 11 struct SPlay 12 { 13 int size,val; 14 SPlay *ch[2],*pa; 15 SPlay(){}; 16 SPlay(int x=0) 17 { 18 size=1;val=x; 19 } 20 }*Root,*null; 21 SPlay* Newnode(int x) 22 { 23 SPlay *y=new SPlay(x); 24 y->ch[0]=y->ch[1]=y->pa=null; 25 return y; 26 } 27 void Maintain(SPlay *t) 28 { 29 t->size=t->ch[0]->size+t->ch[1]->size+1; 30 } 31 int Rank(int x) 32 { 33 SPlay *rt=Root; 34 int res=0; 35 while(rt!=null) 36 { 37 if(x>rt->val) 38 { 39 res+=rt->ch[0]->size+1; 40 rt=rt->ch[1]; 41 } 42 else rt=rt->ch[0]; 43 } 44 return res; 45 } 46 SPlay* Kth(int x) 47 { 48 SPlay *rt=Root; 49 while(rt!=null) 50 { 51 if(rt->ch[0]->size+1==x)return rt; 52 if(rt->ch[0]->size+1>x)rt=rt->ch[0]; 53 else 54 { 55 x-=rt->ch[0]->size+1; 56 rt=rt->ch[1]; 57 } 58 } 59 return null; 60 } 61 int Islson(SPlay *x) 62 { 63 return x->pa->ch[0]==x; 64 } 65 void Rotate(SPlay *x,int d) 66 { 67 SPlay *y=x->ch[d^1]; 68 if(x->pa!=null)x->pa->ch[Islson(x)^1]=y; 69 else Root=y; 70 y->pa=x->pa; 71 x->ch[d^1]=y->ch[d]; 72 if(y->ch[d]!=null)y->ch[d]->pa=x; 73 y->ch[d]=x; 74 x->pa=y; 75 Maintain(x);Maintain(y); 76 } 77 void Splay(SPlay *x,SPlay *t=null) 78 { 79 for(SPlay *rt=x->pa;rt!=t;rt=x->pa) 80 { 81 if(rt->pa==t) 82 { 83 Rotate(rt,Islson(x)); 84 return; 85 } 86 if(Islson(x)==Islson(rt))Rotate(rt->pa,Islson(x)); 87 else Rotate(rt,Islson(x)); 88 Rotate(x->pa,Islson(x)); 89 } 90 } 91 void Insert(int x) 92 { 93 int pos=Rank(x); 94 Splay(Kth(pos));Splay(Kth(pos+1),Root); 95 SPlay *y=Newnode(x); 96 Root->ch[1]->ch[0]=y; 97 y->pa=Root->ch[1]; 98 Maintain(Root->ch[1]);Maintain(Root); 99 } 100 void Delete(int x) 101 { 102 int pos=Rank(x)+1; 103 Splay(Kth(pos-1));Splay(Kth(pos+1),Root); 104 Root->ch[1]->ch[0]=null; 105 Maintain(Root->ch[1]);Maintain(Root); 106 } 107 int n; 108 int haha() 109 { 110 freopen("phs.in","r",stdin); 111 freopen("phs.out","w",stdout); 112 null=new SPlay(0); 113 null->size=0; 114 Root=Newnode(-INF); 115 rs(Root)=Newnode(INF); 116 rs(Root)->pa=Root; 117 scanf("%d",&n); 118 for(int i=1;i<=n;i++) 119 { 120 int opt,x;scanf("%d%d",&opt,&x); 121 switch(opt) 122 { 123 case 1:Insert(x);break; 124 case 2:Delete(x);break; 125 case 3:printf("%d\n",Rank(x)-1+1);break; 126 case 4:printf("%d\n",Kth(x+1)->val);break; 127 case 5:printf("%d\n",Kth(Rank(x))->val);break; 128 case 6:printf("%d\n",Kth(Rank(x+1)+1)->val);break; 129 } 130 } 131 //while(1); 132 } 133 int Zhizhangheng=haha(); 134 int main(){;}
SBT
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 #define ls(x) (x->ch[0]) 8 #define rs(x) (x->ch[1]) 9 #define size(x) ((x) ? (x->size) : (0)) 10 struct SBT 11 { 12 int val,cnt,size; 13 SBT *ch[2]; 14 SBT(int x) 15 { 16 cnt=1;size=1;val=x; 17 ch[0]=ch[1]=NULL; 18 } 19 void Update() 20 { 21 size=cnt; 22 if(ch[0])size+=ch[0]->size; 23 if(ch[1])size+=ch[1]->size; 24 } 25 }*root; 26 void Rotate(SBT* &rt,bool lr) 27 { 28 SBT *t=rt->ch[lr]; 29 rt->ch[lr]=t->ch[lr^1];t->ch[lr^1]=rt;rt=t; 30 rt->ch[lr^1]->Update();rt->Update(); 31 } 32 void Maintain(SBT* &rt) 33 { 34 if(!rt)return; 35 if(!rt->ch[0]&&!rt->ch[1])return; 36 if(!ls(rt)) 37 { 38 if(rt->ch[1]->ch[0]||rt->ch[1]->ch[1])Rotate(rt,1); 39 return; 40 } 41 if(!rs(rt)) 42 { 43 if(rt->ch[0]->ch[0]||rt->ch[0]->ch[1])Rotate(rt,0); 44 return; 45 } 46 if(size(rt->ch[0])<size(rt->ch[1]->ch[0])) 47 { 48 Rotate(rt->ch[1],0); 49 Rotate(rt,1); 50 Maintain(ls(rt));Maintain(rs(rt)); 51 return; 52 } 53 if(size(ls(rt) ) <size(rs(rs(rt) ) ) ) 54 { 55 Rotate(rt,1); 56 Maintain(rs(rt));Maintain(rt); 57 return; 58 } 59 if(size(rs(rt) ) <size(ls(ls(rt) ) ) ) 60 { 61 Rotate(rt,0); 62 Maintain(ls(rt));Maintain(rt); 63 return; 64 } 65 if(size(rs(rt) ) <size(rs(ls(rt) ) ) ) 66 { 67 Rotate(ls(rt),1); 68 Rotate(rt,0); 69 Maintain(ls(rt));Maintain(rs(rt)); 70 return; 71 } 72 } 73 void Insert(SBT* &rt,int x) 74 { 75 if(rt==NULL) 76 { 77 rt=new SBT(x); 78 return; 79 } 80 if(x<rt->val) 81 { 82 Insert(ls(rt),x); 83 rt->size++; 84 Maintain(rt); 85 return; 86 } 87 if(x>rt->val) 88 { 89 Insert(rs(rt),x); 90 rt->size++; 91 Maintain(rt); 92 return; 93 } 94 rt->size++;rt->cnt++; 95 } 96 void Delete(SBT* &rt,int x) 97 { 98 if(x==rt->val) 99 { 100 if(rt->cnt>1) 101 { 102 rt->cnt--;rt->size--; 103 return; 104 } 105 int k=0;bool ok=0,lr; 106 if(ls(rt)) 107 { 108 k=size(ls(rt)); 109 ok=1;lr=0; 110 } 111 if(rs(rt)&&size(rs(rt))>k) 112 { 113 ok=1; 114 lr=1; 115 } 116 if(!ok) 117 { 118 delete rt;rt=NULL; 119 return; 120 } 121 Rotate(rt,lr);Delete(rt->ch[lr^1],x); 122 rt->Update(); 123 return; 124 } 125 if(x<rt->val) 126 { 127 Delete(ls(rt),x); 128 rt->Update(); 129 } 130 else 131 { 132 Delete(rs(rt),x); 133 rt->Update(); 134 } 135 } 136 int Kth(int x) 137 { 138 SBT *rt=root; 139 while(rt) 140 { 141 if(size(ls(rt))>=x) 142 { 143 rt=ls(rt); 144 continue; 145 } 146 if(size(ls(rt))+rt->cnt>=x)return rt->val; 147 else 148 { 149 x-=size(ls(rt))+rt->cnt; 150 rt=rs(rt); 151 } 152 } 153 return -1; 154 } 155 int Rank(int x) 156 { 157 SBT *rt=root; 158 int res=0; 159 while(rt) 160 { 161 if(x==rt->val)return res+size(ls(rt)); 162 if(x<rt->val)rt=ls(rt); 163 else 164 { 165 res+=size(ls(rt))+rt->cnt; 166 rt=rs(rt); 167 } 168 } 169 return res; 170 } 171 int haha() 172 { 173 freopen("phs.in","r",stdin); 174 freopen("phs.out","w",stdout); 175 int n;scanf("%d",&n); 176 for(int i=1;i<=n;i++) 177 { 178 int opt,x;scanf("%d%d",&opt,&x); 179 switch(opt) 180 { 181 case 1:Insert(root,x);break; 182 case 2:Delete(root,x);break; 183 case 3:printf("%d\n",Rank(x)+1);break; 184 case 4:printf("%d\n",Kth(x));break; 185 case 5:printf("%d\n",Kth(Rank(x)));break; 186 case 6:printf("%d\n",Kth(Rank(x+1)+1));break; 187 } 188 } 189 //while(1); 190 } 191 int SBLVCHAO=haha(); 192 int main(){;}
替罪羊树
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int maxn=200005; 7 const double alpha=0.75; 8 struct Scapegoat_Tree 9 { 10 Scapegoat_Tree *ch[2]; 11 int key,size,cover,ext; 12 void Update() 13 { 14 size=ch[0]->size+ch[1]->size+ext; 15 cover=ch[0]->cover+ch[1]->cover+1; 16 } 17 bool bad() 18 { 19 return ch[0]->cover>=cover*alpha+5||ch[1]->cover>=cover*alpha+5; 20 } 21 }Mem[maxn],*null,*root; 22 Scapegoat_Tree *Stack[maxn];int pnt; 23 Scapegoat_Tree *lst[maxn];int len; 24 inline void Init() 25 { 26 root=null=Mem; 27 null->size=null->cover=0; 28 null->ch[0]=null->ch[1]=null; 29 for(int i=1;i<maxn;i++)Stack[++pnt]=Mem+i; 30 } 31 inline Scapegoat_Tree *New(int key) 32 { 33 Scapegoat_Tree *t=Stack[pnt--]; 34 t->ch[0]=t->ch[1]=null; 35 t->size=t->cover=t->ext=1; 36 t->key=key; 37 return t; 38 } 39 inline void Travel(Scapegoat_Tree *p) 40 { 41 if(p==null)return; 42 Travel(p->ch[0]); 43 if(p->ext)lst[++len]=p; 44 Travel(p->ch[1]); 45 } 46 inline Scapegoat_Tree* Divide(int l,int r) 47 { 48 if(l>r)return null; 49 int mid=(l+r)>>1; 50 lst[mid]->ch[0]=Divide(l,mid-1); 51 lst[mid]->ch[1]=Divide(mid+1,r); 52 lst[mid]->Update(); 53 return lst[mid]; 54 } 55 inline void Rebuild(Scapegoat_Tree* &p) 56 { 57 len=0;Travel(p);p=Divide(1,len); 58 } 59 inline Scapegoat_Tree **Insert(Scapegoat_Tree* &p,int key) 60 { 61 if(p==null) 62 { 63 p=New(key); 64 return &null; 65 } 66 p->size++;p->cover++; 67 Scapegoat_Tree **ret=Insert(p->ch[key>=p->key],key); 68 if(p->bad())ret=&p; 69 return ret; 70 } 71 inline void Delete(Scapegoat_Tree *p,int k) 72 { 73 p->size--; 74 if(p->ext&&k==p->ch[0]->size+1)return void(p->ext=0); 75 if(k<=p->ch[0]->size)Delete(p->ch[0],k); 76 else Delete(p->ch[1],k-p->ch[0]->size-p->ext); 77 } 78 inline int Kth(int k) 79 { 80 Scapegoat_Tree *p=root; 81 while(p!=null) 82 { 83 if(p->ext&&k==p->ch[0]->size+1)return p->key; 84 else if(p->ch[0]->size>=k)p=p->ch[0]; 85 else 86 { 87 k-=p->ch[0]->size+p->ext; 88 p=p->ch[1]; 89 } 90 } 91 } 92 inline int Rank(int val) 93 { 94 Scapegoat_Tree *p=root;int ret=1; 95 while(p!=null) 96 { 97 if(p->key>=val)p=p->ch[0]; 98 else 99 { 100 ret+=p->ch[0]->size+p->ext; 101 p=p->ch[1]; 102 } 103 } 104 return ret; 105 } 106 inline void Insert(int val) 107 { 108 Scapegoat_Tree **p=Insert(root,val); 109 if (*p!=null) Rebuild(*p); 110 } 111 void Erase_Kth(int k) 112 { 113 Delete(root,k); 114 if(root->size<alpha*root->cover)Rebuild(root); 115 } 116 void Erase(int k) 117 { 118 Erase_Kth(Rank(k)); 119 } 120 int haha() 121 { 122 freopen("phs.in","r",stdin); 123 freopen("phs.out","w",stdout); 124 Init(); 125 int n;scanf("%d",&n); 126 for(int i=1;i<=n;i++) 127 { 128 int opt,x;scanf("%d%d",&opt,&x); 129 switch(opt) 130 { 131 case 1:Insert(x);break; 132 case 2:Erase(x);break; 133 case 3:printf("%d\n",Rank(x));break; 134 case 4:printf("%d\n",Kth(x));break; 135 case 5:printf("%d\n",Kth(Rank(x)-1));break; 136 case 6:printf("%d\n",Kth(Rank(x+1)));break; 137 } 138 } 139 } 140 int sb=haha(); 141 int main(){;}
01Trie
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define ls(x) (ch[x][0]) 7 #define rs(x) (ch[x][1]) 8 const int maxn=120000*24; 9 int ch[maxn][2],size[maxn],cnt,root; 10 int n,fix,full; 11 void Insert(int x,int add) 12 { 13 x+=fix;int rt=root; 14 for(int i=full;~i;i--) 15 { 16 bool op=x>>i&1; 17 if(!ch[rt][op])ch[rt][op]=++cnt; 18 rt=ch[rt][op]; 19 size[rt]+=add; 20 } 21 } 22 int Rank(int x) 23 { 24 x+=fix; 25 int res=0,rt=root; 26 for(int i=full;~i;i--) 27 { 28 bool op=x>>i&1; 29 if(op) 30 { 31 res+=size[ls(rt)]; 32 rt=rs(rt); 33 } 34 else rt=ls(rt); 35 } 36 return res; 37 } 38 int Kth(int k) 39 { 40 int res=0,rt=root; 41 for(int i=full;~i;i--) 42 { 43 if(k>size[ls(rt)]) 44 { 45 k-=size[ls(rt)]; 46 res|=1<<i; 47 rt=rs(rt); 48 } 49 else rt=ls(rt); 50 } 51 return res-fix; 52 } 53 int haha() 54 { 55 freopen("phs.in","r",stdin);freopen("phs.out","w",stdout); 56 int n;scanf("%d",&n); 57 fix=1e7;full=24; 58 root=++cnt; 59 while(n--) 60 { 61 int opt,x;scanf("%d%d",&opt,&x); 62 switch(opt) 63 { 64 case 1:Insert(x,1);break; 65 case 2:Insert(x,-1);break; 66 case 3:printf("%d\n",Rank(x)+1);break; 67 case 4:printf("%d\n",Kth(x));break; 68 case 5:printf("%d\n",Kth(Rank(x)));break; 69 case 6:printf("%d\n",Kth(Rank(x+1)+1));break; 70 } 71 } 72 } 73 int sb=haha(); 74 int main(){;}
无旋Treap
1 #include<cstdio> 2 #include<algorithm> 3 #define r register 4 namespace Treap 5 { 6 inline int rand() 7 { 8 static int x=23333; 9 return x^=x<<13,x^=x>>17,x^=x<<5; 10 } 11 struct node 12 { 13 node *ch[2]; 14 int val,pri,sz; 15 node(int val=0):val(val)//鍐欏?杈瑰氨瀵逛簡鈥︹€﹀ソ鐜勫?鍟娾€︹€ 16 { 17 pri=rand(); 18 ch[0]=ch[1]=NULL; 19 sz=1; 20 } 21 inline void update() 22 { 23 sz=1; 24 if(ch[0])sz+=ch[0]->sz; 25 if(ch[1])sz+=ch[1]->sz; 26 } 27 }*root; 28 inline int size(node *x) 29 { 30 return x?x->sz:0; 31 } 32 node* merge(node *a,node *b) 33 { 34 if(!a)return b;if(!b)return a; 35 if(a->pri<b->pri) 36 { 37 a->ch[1]=merge(a->ch[1],b); 38 a->update(); 39 return a; 40 } 41 else 42 { 43 b->ch[0]=merge(a,b->ch[0]); 44 b->update(); 45 return b; 46 } 47 } 48 typedef std::pair<node*,node*>Npair; 49 Npair split(node *x,int k) 50 { 51 if(!x)return Npair(NULL,NULL); 52 r Npair y; 53 if(size(x->ch[0])>=k) 54 { 55 y=split(x->ch[0],k); 56 x->ch[0]=y.second; 57 x->update(); 58 y.second=x; 59 } 60 else 61 { 62 y=split(x->ch[1],k-size(x->ch[0])-1); 63 x->ch[1]=y.first; 64 x->update(); 65 y.first=x; 66 } 67 return y; 68 } 69 inline int Kth(int k) 70 { 71 r Npair x=split(root,k-1); 72 r Npair y=split(x.second,1); 73 r node *ans=y.first; 74 root=merge(merge(x.first,ans),y.second); 75 return ans->val; 76 } 77 int Rank(node *x,int k) 78 { 79 if(!x)return 0; 80 return k<x->val?Rank(x->ch[0],k):Rank(x->ch[1],k)+size(x->ch[0])+1; 81 } 82 inline void Insert(int val) 83 { 84 r int k=Rank(root,val); 85 r Npair x=split(root,k); 86 r node *a=new node(val); 87 root=merge(merge(x.first,a),x.second); 88 } 89 inline void Delete(int val) 90 { 91 r int k=Rank(root,val); 92 r Npair x=split(root,k-1); 93 r Npair y=split(x.second,1); 94 r node *ans=y.first; 95 root=merge(x.first,y.second); 96 delete ans; 97 ans=NULL; 98 } 99 inline int prefix(int val) 100 { 101 r int k=Rank(root,val-1); 102 return Kth(k); 103 } 104 inline int suffix(int val) 105 { 106 r int k=Rank(root,val); 107 return Kth(k+1); 108 } 109 } 110 int haha() 111 { 112 freopen("phs.in","r",stdin); 113 freopen("phs.out","w",stdout); 114 int n;scanf("%d",&n); 115 while(n--) 116 { 117 r int opt,x;scanf("%d%d",&opt,&x); 118 switch(opt) 119 { 120 case 1:Treap::Insert(x);break; 121 case 2:Treap::Delete(x);break; 122 case 3:printf("%d\n",Treap::Rank(Treap::root,x-1)+1);break; 123 case 4:printf("%d\n",Treap::Kth(x));break; 124 case 5:printf("%d\n",Treap::prefix(x));break; 125 case 6:printf("%d\n",Treap::suffix(x));break; 126 } 127 } 128 } 129 int sb=haha(); 130 int main(){;}
有没有哪位大神用别的水过的欢迎留言……
Tyvj 1730 论我们有多少种方法调戏普通平衡树（其实是备忘录）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。