普通平衡树代码。。。Treap

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 
  6 using namespace std;
  7 struct node
  8 {
  9     int data;
 10     int key;
 11     node* ls;
 12     node* rs;
 13     int size;
 14 
 15     node()
 16     {
 17         key=rand();
 18     }
 19 }no[300010];
 20 
 21 void update(node* now)
 22 {
 23     now->size=1;
 24     if (now->ls) now->size+=now->ls->size;
 25     if (now->rs) now->size+=now->rs->size;
 26 }
 27 
 28 node* merge(node* a,node* b)
 29 {
 30     if (!a) {update(b);return b;}
 31     if (!b) {update(a);return a;}
 32     if (a->key<b->key)
 33     {
 34         a->rs=merge(a->rs,b);
 35         update(a);
 36         return a;
 37     }
 38     else
 39     {
 40         b->ls=merge(a,b->ls);
 41         update(b);
 42         return b;
 43     }
 44 }
 45 
 46 struct nodepair
 47 {
 48     node* l;
 49     node* r;
 50 
 51     nodepair(node* a,node* b)
 52     {
 53         l=a;
 54         r=b;
 55     }
 56 };
 57 
 58 nodepair split(node* a,int k)
 59 {
 60     if (!a) return nodepair(NULL,NULL);
 61     if (a->data<=k)
 62     {
 63         nodepair km=split(a->rs,k);
 64         a->rs=km.l;
 65         update(a);
 66         return nodepair(a,km.r);
 67     }    
 68     else
 69     {
 70         nodepair km=split(a->ls,k);
 71         a->ls=km.r;
 72         update(a);
 73         return nodepair(km.l,a);
 74     }
 75 }
 76 
 77 nodepair splitTh(node* a,int k)
 78 {
 79     if (!a) return nodepair(NULL,NULL);
 80     if (!k) return nodepair(NULL,a);
 81     if (a->ls)
 82     {
 83         if (a->ls->size>=k)
 84         {
 85             nodepair km=splitTh(a->ls,k);
 86             a->ls=km.r;
 87             update(a);
 88             return nodepair(km.l,a);
 89         }
 90         else
 91         {
 92             nodepair km=splitTh(a->rs,k-a->ls->size-1);
 93             a->rs=km.l;
 94             update(a);
 95             return nodepair(a,km.r);
 96         }
 97     }
 98     else
 99     {
100         nodepair km=splitTh(a->rs,k-1);
101         a->rs=km.l;
102         update(a);
103         return nodepair(a,km.r);
104     }
105 }
106 
107 int cnt=-1;
108 node* insert(node* root,int newdata)
109 {
110     node* q=&no[++cnt];
111     q->data=newdata;
112     nodepair km=split(root,newdata);
113     return merge(km.l,merge(q,km.r));
114 }
115 
116 node* delate(node* root,int newdata)
117 {
118     nodepair km=split(root,newdata-1);
119     nodepair km2=splitTh(km.r,1);
120     return merge(km.l,km2.r);
121 }
122 
123 int getKth(node* now,int k)
124 {
125     if (!now) return -123456789;
126     if (now->ls)
127     {
128         if (now->ls->size<k-1)
129             return getKth(now->rs,k-now->ls->size-1);
130         if (now->ls->size==k-1)
131             return now->data;
132         if (now->ls->size>k-1)
133             return getKth(now->ls,k);
134     }
135     else
136     {
137         if (k==1) return now->data;
138         return getKth(now->rs,k-1);
139     }
140 }
141 
142 node* Search(node* root,int k,int* ans)
143 {
144     nodepair km=split(root,k-1);
145     if (km.l)
146         *ans=km.l->size+1;
147     else
148         *ans=1;
149     return merge(km.l,km.r);
150 }
151 
152 node* getQQ(node* root,int data,int* ans)
153 {
154     nodepair km=split(root,data-1);
155     nodepair km2=splitTh(km.l,km.l->size-1);
156     *ans=km2.r->data;
157     return merge(km2.l,merge(km2.r,km.r));
158 }
159 
160 node* getHJ(node* root,int data,int* ans)
161 {
162     nodepair km=split(root,data);
163     nodepair km2=splitTh(km.r,1);
164     *ans=km2.l->data;
165     return merge(km.l,merge(km2.l,km2.r));
166 }
167 
168 int main()
169 {
170     node* root=NULL;
171     int n,cmd,k;
172     scanf("%d",&n);
173     for (int i=1;i<=n;++i)
174     {
175         scanf("%d%d",&cmd,&k);
176         if (cmd==1){root=insert(root,k);}
177         if (cmd==2){root=delate(root,k);}
178         if (cmd==3)
179         {
180             int ans=0;
181             root=Search(root,k,&ans);
182             printf("%d\n",ans);
183         }
184         if (cmd==4)
185         {
186             printf("%d\n",getKth(root,k));
187         }
188         if (cmd==5)
189         {
190             int ans=0;
191             root=getQQ(root,k,&ans);
192             printf("%d\n",ans);
193         }
194         if (cmd==6)
195         {
196             int ans=0;
197             root=getHJ(root,k,&ans);
198             printf("%d\n",ans);
199         }
200     }
201     return 0;
202 }