无旋treap（可持久化）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<vector>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 const int MAXN=2000000+10;
 10 struct NODE{//小根堆treap 
 11     NODE *ch[2];
 12     int v,r,s;
 13     #define size(x) ((x)?(x)->s:0)
 14     NODE(int v=0):v(v){r=rand();ch[0]=ch[1]=NULL;s=1;}
 15     bool operator < (const NODE &rhs) const {
 16         return r < rhs.r;
 17     }
 18     int cmp(int x){
 19         if(x == v) return -1;
 20         return x < v ? 0:1;
 21     }
 22     void mt(){
 23         s=1;
 24         s+=size(ch[0]);
 25         s+=size(ch[1]);
 26     }
 27 }*root;
 28 //无旋treap相关 
 29 typedef pair<NODE*,NODE*> droot;
 30 droot split(NODE *x,int k){
 31     if(x == NULL) return droot(NULL,NULL);
 32     droot r;
 33     if(size(x->ch[0]) >= k){
 34         r=split(x->ch[0],k);
 35         x->ch[0]=r.second;
 36         x->mt();
 37         r.second=x;
 38     }
 39     else {
 40         r=split(x->ch[1],k-size(x->ch[0])-1);
 41         x->ch[1]=r.first;
 42         x->mt();
 43         r.first=x;
 44     }
 45     return r;
 46 }
 47 NODE *merge(NODE *a,NODE *b){
 48     if(a == NULL) return b;
 49     if(b == NULL) return a;
 50     if(a->r < b->r){
 51         a->ch[1]=merge(a->ch[1],b);
 52         a->mt();
 53         return a;
 54     }
 55     else {
 56         b->ch[0]=merge(a,b->ch[0]);
 57         b->mt();
 58         return b;
 59     }
 60 }
 61 NODE *build(int *a){//类似于笛卡尔树 
 62     static NODE *stack[MAXN],*x,*last;
 63     int p=0;
 64     for(int i=1;i<=a[0];i++){
 65         x=new NODE(a[i]);
 66         last=NULL;
 67         while(p && stack[p]->r > x->r){
 68             stack[p]->mt();
 69             last=stack[p];
 70             stack[p--]=NULL;
 71         }
 72         if(p) stack[p]->ch[1]=x;
 73         x->ch[0]=last;
 74         stack[++p]=x;
 75     }
 76     while(p) stack[p--]->mt();
 77     return stack[1];
 78 }
 79 //名次树相关
 80 int rank(NODE *x,int v){
 81     if(x == NULL) return 0;
 82     if(v < x->v) return rank(x->ch[0],v);
 83     else rank(x->ch[1],v)+size(x->ch[0])+1;
 84 } 
 85 int kth(int k){
 86     droot x=split(root,k-1);
 87     droot y=split(x.second,1);
 88     NODE *ans=y.first;
 89     root=merge(merge(x.first,ans),y.second);
 90     return ans->v;
 91 }
 92 void insert(int v){
 93     int k=rank(root,v);
 94     droot x=split(root,k);
 95     NODE *n=new NODE(v);
 96     root=merge(merge(x.first,n),x.second);
 97 }
 98 void remove(int k){
 99     droot x=split(root,k-1);
100     droot y=split(x.second,1);
101     root=merge(x.first,y.second);
102 }
103 
104 int a[MAXN],M,x,y;
105  
106 int main(){
107     freopen("bst.in","r",stdin);
108     freopen("bst.out","w",stdout);
109      
110     scanf("%d",a);
111     for(int i=1;i<=a[0];i++) scanf("%d",a+i);
112     sort(a+1,a+1+a[0]);
113     root=build(a);
114      
115     scanf("%d",&M);
116     while(M--){
117         char ch=getchar();
118         while(ch!='Q' && ch!='A' && ch!='D') ch=getchar();
119         scanf("%d",&x);
120         if(ch=='Q') printf("%d
",kth(x));
121         if(ch=='A') insert(x);
122         if(ch=='D') remove(x);
123     }
124     return(0);
125 }