无旋 Treap
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <ctime>
- #include <cstdlib>
- using namespace std;
- const int maxn=100100,inf=0x7fffffff;
- struct Treap
- {
- Treap* ch[2];
- int key,val,size;
- Treap(int v){size=1,val=v,key=rand();ch[0]=ch[1]=NULL;}
- inline void tain()
- {size=1+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0);}
- }*root;
- typedef pair<Treap*,Treap*> D;
- inline int size(Treap *o){return o?o->size:0;}
- Treap *Merge(Treap *a,Treap* b)
- {
- if(!a)return b;
- if(!b)return a;
- if(a->key <b->key)
- {
- a->ch[1]=Merge(a->ch[1],b);
- a->tain();
- return a;
- }
- else
- {
- b->ch[0]=Merge(a,b->ch[0]);
- b->tain();
- return b;
- }
- }
- D Split(Treap *o,int k)
- {
- if(!o)return D(NULL,NULL);
- D y;
- if(size(o->ch[0])>=k)
- {
- y=Split(o->ch[0],k);
- o->ch[0]=y.second;
- o->tain();
- y.second=o;
- }
- else
- {
- y=Split(o->ch[1],k-size(o->ch[0])-1);
- o->ch[1]=y.first;
- o->tain();
- y.first=o;
- }
- return y;
- }
- int Getkth(Treap *o,int v)
- {
- if(o==NULL)return 0;
- return(o->val>=v)?Getkth(o->ch[0],v):Getkth(o->ch[1],v)+size(o->ch[0])+1;
- }
- inline int Findkth(int k)
- {
- D x=Split(root,k-1);
- D y=Split(x.second,1);
- Treap *ans=y.first;
- root=Merge(Merge(x.first,ans),y.second);
- return ans!=NULL?ans->val:0;
- }
- inline void Insert(int v)
- {
- int k=Getkth(root,v);
- D x=Split(root,k);
- Treap *o=new Treap(v);
- root=Merge(Merge(x.first,o),x.second);
- }
- void Delete(int v)
- {
- int k=Getkth(root,v);
- D x=Split(root,k);
- D y=Split(x.second,1);
- root=Merge(x.first,y.second);
- }
- int main()
- {
- int m,opt,x;scanf("%d",&m);
- while(m--)
- {
- scanf("%d%d",&opt,&x);
- switch(opt)
- {
- case 1:Insert(x);break;
- case 2:Delete(x);break;
- case 3:printf("%d\n",Getkth(root,x)+1);break;
- case 4:printf("%d\n",Findkth(x));break;
- case 5:printf("%d\n",Findkth(Getkth(root,x)));break;
- case 6:printf("%d\n",Findkth(Getkth(root,x+1)+1));break;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3090001.html