splay模板

  1 #include"bits/stdc++.h"
  2 using namespace std;
  3 
  4 
  5 int n,m;
  6 int root=0; int tot;
  7 const int nn = 200000;
  8 int cnt[nn]; int v[nn];
  9 int ch[nn][2]; int fa[nn];
 10 int size[nn];
 11 
 12 inline void push(int x)
 13 {
 14     size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
 15     return ;
 16 }
 17 inline void rot(int x,int d)
 18 {
 19     int y=fa[x]; int z=fa[y];
 20     ch[y][d^1]=ch[x][d];
 21     fa[ch[x][d]]=y;
 22     ch[x][d]=y;
 23     fa[y]=x;
 24     push(y),push(x);
 25     int t = ch[z][1]==y;
 26     if (z)ch[z][t]=x;
 27     fa[x]=z;
 28     if (z)push(z);
 29     return ;
 30     
 31 }
 32 
 33 
 34 inline void splay(int x,int goal=0)
 35 {
 36     while (fa[x]!=goal)
 37     {
 38         int y=fa[x]; int z=fa[y];
 39         if (z==goal)
 40         {
 41             rot(x,(ch[y][1]==x)^1); break;  // 有个^
 42             
 43         }
 44         else 
 45         {
 46             if (ch[z][1]==y) 
 47             if (ch[y][1]==x)rot(y,0),rot(x,0);
 48             else rot(x,1),rot(x,0);
 49             else if (ch[y][0]==x)rot(y,1),rot(x,1);
 50             else rot(x,0),rot(x,1); 
 51         }
 52     }
 53     if (!goal)root=x;
 54 }
 55 
 56 inline void insert(int x)
 57 {
 58     int now = root;
 59     while (1)
 60     {
 61         if (v[now]==x)
 62         {
 63         cnt[now]++,splay(now);push(now);tot++;
 64         break;
 65         }
 66         if (!ch[now][x>v[now]])
 67         {ch[now][x>v[now]]=++tot,cnt[tot]=1,size[tot]=1,v[tot]=x;    
 68         fa[tot]=now;splay(tot);
 69     break;}
 70         now=ch[now][x>v[now]];        
 71     }
 72 }
 73 
 74 int find(int x)
 75 {   int now =root;
 76     while (1)
 77     {
 78         if (x<=size[ch[now][0]])now=ch[now][0];
 79         else if (x>size[ch[now][0]]+cnt[now])x-=size[ch[now][0]]+cnt[now],
 80                                              now=ch[now][1];
 81        else return now;
 82     }
 83 }
 84 
 85 void print(int x)
 86 {
 87     if (!x)return ;
 88     int l=ch[x][0],r=ch[x][1];
 89     cout<<l<<" "<<r<<" "<<v[l]<<" "<<v[r]<<" "<<fa[x]<<" "<<v[x]<<" "<<size[x]<<endl;
 90     print(l);
 91     print(r); 
 92 }
 93 
 94 int main()
 95 {
 96     cin>>n;
 97     
 98     for (int i=1;i<=n;i++)
 99     {
100         int x;scanf("%d",&x);
101         if (!root)root=++tot,cnt[tot]=1,size[tot]=1,v[tot]=x;
102         else insert(x);
103         
104 
105     }cin>>m;
106     while (m--)
107     {
108         char s[10];
109         cin>>s;
110         if (s[0]=='a')
111         {
112             int x;scanf("%d",&x);insert(x);
113             
114         }else printf("%d
",v[find(tot/2+(tot&1))]);
115     }
116     
117 }