Treap 的各种操作，模板题，要再写几遍

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 9 using namespace std; 10 11 class Treap 12 { 13 private: 14 struct Treap_Point 15 { 16 int l,r,val,size,key,num; 17 Treap_Point(){l=r=val=size=key=num=0;} 18 }; 19 Treap_Point d[210000]; 20 int root,cnt; 21 pair
            
              tmp; 22 23 void update(const int t) 24 { 25 d[t].size=d[d[t].l].size+ 26 d[d[t].r].size+d[t].num; 27 return ; 28 } 29 30 void turn_R(int & t) 31 { 32 int temp=d[t].l;d[t].l=d[temp].r;d[temp].r=t; 33 d[temp].size=d[t].size;update(t);t=temp;return ; 34 } 35 36 void turn_L(int & t) 37 { 38 int temp=d[t].r;d[t].r=d[temp].l;d[temp].l=t; 39 d[temp].size=d[t].size;update(t);t=temp;return ; 40 } 41 42 void insert(int & t,const int x) 43 { 44 if(!t) 45 { 46 cnt++;t=cnt;d[t].size=d[t].num=1; 47 d[t].val=x,d[t].key=rand(); 48 return ; 49 } 50 d[t].size++; 51 if(d[t].val==x)d[t].num++; 52 else if(x<=d[t].val) 53 { 54 insert(d[t].l,x); 55 if(d[d[t].l].key
             
              1) 71 { 72 d[t].num--;d[t].size--;return ; 73 } 74 if(d[t].l*d[t].r==0)t=d[t].l+d[t].r; 75 else if(d[d[t].l].key
              
               d[d[t].l].size+d[t].num) 90 return get(d[t].r,x-d[d[t].l].size-d[t].num); 91 return d[t].val; 92 } 93 94 int upper_bound(const int & t,const int x,const int step) 95 { 96 if(t==0)return 0; 97 if(x
               
                =d[t].val)upper_bound(d[t].r,x,step+d[d[d[t].r].l].size+d[t].num); 99 else upper_bound(d[t].l,x,step-d[d[d[t].l].r].size-d[d[t].l].num);100 return tmp.second;101 }102 103 int lower_bound(const int & t,const int x,const int step)104 {105 if(t==0)return 0;106 if(x<=d[t].val)tmp=min(tmp,make_pair(d[t].val,step));107 if(x>d[t].val)lower_bound(d[t].r,x,step+d[d[d[t].r].l].size+d[t].num);108 else lower_bound(d[t].l,x,step-d[d[d[t].l].r].size-d[d[t].l].num);109 return tmp.second;110 }111 112 public:113 void insert(const int x)114 {115 insert(root,x);116 }117 void erase(const int x)118 {119 erase(root,x);120 }121 int get(const int x)122 {123 return get(root,x);124 }125 int upper_bound(const int x)126 {127 tmp=make_pair(0x7fffffff,0);128 return upper_bound(root,x,d[d[root].l].size+1);129 }130 int lower_bound(const int x)131 {132 tmp=make_pair(0x7fffffff,0);133 return lower_bound(root,x,d[d[root].l].size+1);134 }135 }S;136 137 int n;138 139 int main()140 {141 int i,op,x;142 143 scanf("%d",&n);144 145 S.insert(0x7ffffff0);146 for(i=1;i<=n;++i)147 {148 scanf("%d%d",&op,&x);149 if(op==1)S.insert(x);150 if(op==2)S.erase(x);151 if(op==3)printf("%d\n",S.lower_bound(x));152 if(op==4)printf("%d\n",S.get(x));153 if(op==5)printf("%d\n",S.get(S.lower_bound(x)-1));154 if(op==6)printf("%d\n",S.get(S.upper_bound(x)));155 }156 157 return 0;158 }