【模板】普通平衡树 Treap

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 using namespace std;
 7 const int N=100010,inf=10000010;
 8 int n;
 9 
10 struct node
11 {
12     node* ch[2];
13     int r,s,v;
14     node(int v):v(v){s=1; r=rand(); ch[0]=ch[1]=NULL;}
15     bool operator < (const node& rhs) const {return r < rhs.r;}
16     int cmp(int x){if(x == v)return -1; return x < v ? 0 : 1 ;}
17     void maintain(){s=1;
18         if(ch[0] != NULL) s+=ch[0]->s; if(ch[1] != NULL) s+=ch[1]->s;
19     }
20 };
21 node* rt=NULL;
22 
23 void rotate(node* &o,int d){
24     node* k=o->ch[d^1];
25     o->ch[d^1]=k->ch[d]; k->ch[d]=o;
26     o->maintain();k->maintain(); o=k;
27 }
28 void ins(node* &o,int x){
29     if(o == NULL){o=new node(x);return ;}
30     int d=(x < o->v ? 0 : 1);ins(o->ch[d],x);
31     if(o->ch[d] > o) rotate(o,d^1); o->maintain();
32 }
33 void del(node* &o,int x){
34     if(o == NULL) return ;
35     int d=o->cmp(x);
36     if(d == -1){
37         if(o->ch[0] != NULL && o->ch[1] != NULL){
38             int d2=(o->ch[1]->r > o->ch[0]->r ? 0 : 1);
39             rotate(o,d2);del(o->ch[d2],x);
40         }
41         else {if(o->ch[0] == NULL) o=o->ch[1];else o=o->ch[0];}
42     }
43     else del(o->ch[d],x); if(o != NULL) o->maintain();
44 }
45 
46 int kth(node *o,int k){
47     if(o == NULL || k > o->s || o <= 0) return 0;
48     int s=(o->ch[0] == NULL ? 0 : o->ch[0]->s);
49     if(k == s+1) return o->v;
50     if(k <= s) return kth(o->ch[0], k);
51     return kth(o->ch[1], k-s-1);
52 }
53 void rank(node *o,int x,int &ans,int k){
54     if(o==NULL) return ;
55     int ss=(o->ch[0] == NULL ? 0 : o->ch[0]->s);
56     if(o->v < x) {rank(o->ch[1],x,ans,k+ss+1); return ;}
57     if(o->v == x) ans=min(ans,k+ss+1);
58     rank(o->ch[0],x,ans,k);
59 }
60 void pre(node* o,int x,int &ans){
61     if(o == NULL) return ;
62     if(o->v < x) {ans=max(o->v, ans); pre(o->ch[1],x,ans); return ;}
63     pre(o->ch[0],x,ans); 
64 }
65 void post(node* o,int x,int &ans){
66     if(o == NULL) return ;
67     if(o->v > x) {ans=min(o->v, ans); post(o->ch[0], x, ans); return ;}
68     post(o->ch[1], x, ans); 
69 }
70 
71 void solve(){
72     n=read();
73     while(n--){
74         int opt=read(),x=read();
75         if(opt == 1) ins(rt, x);
76         if(opt == 2) del(rt, x);
77         if(opt == 4) printf("%d
",kth(rt, x));
78         if(opt == 3) {int ans3=inf; rank(rt, x,ans3,0); printf("%d
",ans3);}
79         if(opt == 5) {int ans5=-inf; pre(rt, x,ans5); printf("%d
",ans5);}
80         if(opt == 6) {int ans6=inf; post(rt, x,ans6); printf("%d
",ans6);}
81     }
82 }