●个人感觉：

• 代码长；
• 函数多；
• （很套路）；
• （很强的Splay，无愧于“区间王”）

●NOI2005维修数列

• 一个可以当模板学习的题，包含了众多操作（函数）：
• 区间插入，删除，更新，翻转，询问信息以及”回收空间”(名字很刚)等。
• update()pushdown() rotate() splay() build() find() split() insert() rec() erase() query() rever() modify()还有main()
• 建议初学Splay者打一打；
• 代码：
• 

    1 #include<queue>
    2 #include<cmath>
    3 #include<cstdio>
    4 #include<cstring>
    5 #include<cstdlib>
    6 #include<iostream>
    7 #include<algorithm>
    8 #define inf 1000000000
    9 #define N 1000005
   10 using namespace std;
   11 int read()
   12 {
   13     int x=0,f=1;char ch=getchar();
   14     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
   15     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
   16     return x*f;
   17 }
   18 int n,m,rt,cnt,k,len,val; char ch[10];
   19 int a[N],id[N],fa[N],c[N][2];
   20 int sum[N],siz[N],v[N],mx[N],lx[N],rx[N];
   21 bool tag[N],rev[N];
   22 queue<int> q;
   23 void update(int x)                                            
   24 {
   25     int l=c[x][0],r=c[x][1];
   26     sum[x]=sum[l]+sum[r]+v[x];
   27     siz[x]=siz[l]+siz[r]+1;
   28     mx[x]=max(mx[l],mx[r]);
   29     mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
   30     lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
   31     rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
   32 }
   33 void pushdown(int x)                                          
   34 {
   35     int l=c[x][0],r=c[x][1];
   36     if(tag[x])
   37     {
   38         rev[x]=tag[x]=0;                          
   39         if(l) tag[l]=1,v[l]=v[x],sum[l]=v[l]*siz[l];
   40         if(r) tag[r]=1,v[r]=v[x],sum[r]=v[r]*siz[r];
   41         if(v[x]>=0)
   42         {
   43             if(l) lx[l]=rx[l]=mx[l]=sum[l];
   44             if(r) lx[r]=rx[r]=mx[r]=sum[r];
   45         }
   46         else 
   47         {
   48             if(l)lx[l]=rx[l]=0,mx[l]=v[x];
   49             if(r)lx[r]=rx[r]=0,mx[r]=v[x];
   50         }
   51     }
   52     if(rev[x])
   53     {
   54         rev[x]^=1;rev[l]^=1;rev[r]^=1;        
   55          swap(lx[l],rx[l]);swap(lx[r],rx[r]); 
   56         swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);
   57     }
   58 }
   59 void rotate(int x,int &k)//Dy×a￡¨μ￥￡? 
   60 {
   61     int y=fa[x],z=fa[y];
   62     int l=(x!=c[y][0]),r=l^1;
   63     if(y==k) k=x;
   64     else c[z][y!=c[z][0]]=x;
   65     fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
   66     c[y][l]=c[x][r]; c[x][r]=y;
   67     update(y); update(x);
   68 }
   69 void splay(int x,int &k) 
   70 {
   71     int y,z;
   72     while(x!=k)
   73     {
   74         y=fa[x],z=fa[y];
   75         if(y!=k)
   76         {
   77             if(c[y][0]==x^c[z][0]==y) rotate(x,k);
   78             else rotate(y,k);
   79         }
   80         rotate(x,k);
   81     }
   82 }
   83 void build(int l,int r,int f)
   84 {
   85     if(l>r) return;
   86     int mid=l+r>>1,now=id[mid],last=id[f];
   87     if(l==r)
   88     {
   89         sum[now]=a[l];
   90         siz[now]=1;
   91         tag[now]=rev[now]=0;
   92         if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];
   93         else lx[now]=rx[now]=0,mx[now]=a[l];
   94     }
   95     build(l,mid-1,mid);build(mid+1,r,mid);
   96     v[now]=a[mid];
   97     fa[now]=last;
   98     c[last][mid>=f]=now;
   99     update(now);
  100 }
  101 int find(int k,int x) 
  102 {
  103     pushdown(k);
  104     if(siz[c[k][0]]+1==x) return k; 
  105     if(siz[c[k][0]]>=x) return find(c[k][0],x);
  106     else return find(c[k][1],x-siz[c[k][0]]-1);
  107 }
  108 int split(int k,int len)
  109 {                                                                                                    
  110     int x=find(rt,k),y=find(rt,k+len+1);
  111     splay(x,rt);splay(y,c[x][1]);
  112     return c[y][0];
  113 }
  114 void insert(int k,int len)
  115 {
  116     for(int i=1;i<=len;i++)
  117     if(!q.empty()) id[i]=q.front(),q.pop();
  118     else id[i]=++cnt;
  119     for(int i=1;i<=len;i++) a[i]=read();
  120     build(1,len,0);
  121     int x=id[1+len>>1];
  122     int z=find(rt,k+1),y=find(rt,k+2);//μúò????a-inf 
  123     splay(z,rt); splay(y,c[z][1]);
  124     fa[x]=y; c[y][0]=x;
  125     update(y);update(fa[y]);
  126 }
  127 void rec(int x) 
  128 {                                                            
  129     if(!x) return;
  130     int l=c[x][0],r=c[x][1];
  131     rec(l); rec(r);
  132     q.push(x);
  133     fa[x]=c[x][0]=c[x][1]=0;
  134     tag[x]=rev[x]=0;
  135 }
  136 void erase(int k,int len)
  137 {
  138     int x=split(k,len),y=fa[x];
  139     rec(x); c[y][0]=0;
  140     update(y);update(fa[y]);
  141 }
  142 void query(int k,int len)
  143 {
  144     int x=split(k,len);
  145     printf("%d\n",sum[x]);
  146 }
  147 void rever(int k,int len)//????·-×a 
  148 {
  149     int x=split(k,len),y=fa[x];
  150     if(!tag[x])
  151     {
  152         rev[x]^=1;                        
  153         swap(lx[x],rx[x]);
  154         swap(c[x][0],c[x][1]);
  155         update(y);update(fa[y]);
  156     }
  157 }
  158 void modify(int k,int len,int val)
  159 {
  160     int x=split(k,len),y=fa[x];
  161     tag[x]=1; v[x]=val;
  162     sum[x]=v[x]*siz[x];
  163     if(v[x]>=0) lx[x]=rx[x]=mx[x]=sum[x];
  164     else lx[x]=rx[x]=0,mx[x]=v[x];
  165     update(y);update(fa[y]);
  166 }
  167 int main()
  168 {
  169     n=read();m=read();
  170     mx[0]=a[1]=a[n+2]=-inf; id[1]=1; id[n+2]=n+2;
  171     for(int i=2;i<=n+1;i++) a[i]=read(),id[i]=i;
  172     build(1,n+2,0);
  173     rt=n+3>>1; cnt=n+2;
  174     while(m-->0)
  175     {
  176         scanf("%s",ch);
  177         if(ch[0]!=‘M‘||ch[2]!=‘X‘) k=read(),len=read();
  178         if(ch[0]==‘I‘) insert(k,len);
  179         if(ch[0]==‘D‘) erase(k,len);
  180         if(ch[0]==‘R‘) rever(k,len);
  181         if(ch[0]==‘G‘) query(k,len);
  182         if(ch[0]==‘M‘)
  183         {
  184             if(ch[2]==‘X‘)printf("%d\n",mx[rt]);
  185             else val=read(),modify(k,len,val);
  186         }
  187     }
  188     return 0;
  189 }

  I‘m here!

   

●宠物收养所（codves 1285）

• 用Splay维护一个权值树，每次进行查找，删除或插入操作,较简单。
• 注意要mod
• 代码：
• 

   1 #include<cstdio>
   2 #include<iostream>
   3 using namespace std;
   4 int rt,size,n,t1,t2,kind;
   5 long long ans;
   6 int fa[80005],tr[80005][2],num[80005];
   7 void rotate(int x,int &k)
   8 {
   9     int y=fa[x],z=fa[y];
  10     int l=(x!=tr[y][0]),r=l^1;
  11     if(y!=k) tr[z][(y!=tr[z][0])]=x;
  12     else k=x;
  13     fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
  14     tr[y][l]=tr[x][r];tr[x][r]=y;
  15 }
  16 void splay(int x,int &k)
  17 {
  18     int y,z;
  19     while(x!=k)
  20     {
  21         y=fa[x],z=fa[y];
  22         if(y!=k)
  23         {
  24             if((x==tr[y][0])^(y==tr[z][0]))rotate(x,k);
  25             else rotate(y,k);    
  26         }
  27         rotate(x,k);
  28     }
  29 }
  30 void ins(int &k,int x,int last)
  31 {
  32     if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}
  33     if(x<num[k])ins(tr[k][0],x,k);else ins(tr[k][1],x,k);
  34 }
  35 void find_pre(int k,int x)
  36 {
  37     if(k==0) return;
  38     if(num[k]<=x){t1=k;find_pre(tr[k][1],x);}
  39     else find_pre(tr[k][0],x);
  40 }
  41 void find_bac(int k,int x)
  42 {
  43     if(k==0) return;
  44     if(num[k]>=x){t2=k;find_bac(tr[k][0],x);}
  45     else find_bac(tr[k][1],x);
  46 }
  47 void del(int x)
  48 {
  49     splay(x,rt);
  50     if(tr[x][0]*tr[x][1]==0) rt=tr[x][0]+tr[x][1];
  51     else
  52     {
  53         int k=tr[x][1];
  54         while(tr[k][0])k=tr[k][0];
  55         tr[k][0]=tr[x][0];fa[tr[x][0]]=k; 
  56         rt=tr[x][1];
  57     }
  58     fa[rt]=0;
  59 }
  60 int main()
  61 {
  62     scanf("%d",&n);int f,x;
  63     for(int i=1;i<=n;i++)
  64     {
  65         scanf("%d%d",&f,&x);
  66         if(!rt){kind=f;ins(rt,x,0);}
  67         else if(kind==f) ins(rt,x,0);
  68         else
  69         {
  70             t1=t2=-1;
  71             find_pre(rt,x);find_bac(rt,x);
  72             if(t1==-1){ans+=num[t2]-x;ans%=1000000;del(t2);}
  73             else if(t2==-1){ans+=x-num[t1];ans%=1000000;del(t1);}
  74             else
  75             {
  76                 if(num[t2]-x>=x-num[t1]) ans+=x-num[t1],del(t1);// μ± a-b==a+bê±￡???a-b 
  77                 else ans+=num[t2]-x,del(t2); ans%=1000000;
  78             }
  79             
  80         }
  81         
  82     }
  83     printf("%d",ans);
  84     return 0;
  85 }

  I‘m still here!

   

●营业额统计（codevs 1296）

• 用Splay维护营业额（权值树），每次先查找小于今日营业额的最大值和大于今日营业额的最小值，（也可以有相等的请况），然后取最优解加入ans中，在插入今日营业额；
• 和上题有点像
• 但不知我的代码为何在codevs上要TLE一组，在COGS上要WA一组和TLE一组（求助！）
• 代码：
• 

   1 #include<cstdio>
   2 #include<iostream>
   3 #include<cstring>
   4 #include<cmath>
   5 #define N 40000
   6 using namespace std;
   7 int fa[N],ch[N][2],num[N];
   8 int n,a,t1,t2,root,sz;
   9 void rotate(int x,int &k)
  10 {   
  11     int y,z,l,r;
  12     z=fa[y=fa[x]];
  13     r=1^(l=(ch[y][1]==x));
  14     if(y==k)k=x;
  15     else ch[z][ch[z][1]==y]=x;
  16     fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
  17     ch[y][l]=ch[x][r];ch[x][r]=y;
  18 }
  19 void splay(int x,int &k)
  20 {
  21     int y,z;
  22     while(x!=k)
  23     {
  24         z=fa[y=fa[x]];
  25         if(y!=k) ch[z][0]==y^ch[y][0]==x?rotate(x,k):rotate(y,k);
  26         rotate(x,k);
  27     }
  28 }
  29 void insert(int x,int last,int &k)
  30 {
  31     if(!k)
  32     {
  33         k=++sz;
  34         num[sz]=x;
  35         fa[k]=last;
  36         splay(k,root);
  37         return;
  38     }
  39     if(num[k]==x)return;
  40     insert(x,k,ch[k][x>num[k]]);
  41 }
  42 void find_fro(int x,int k)
  43 {
  44     if(!k)return;//???e?e
  45     if(num[k]<=x){t1=k;find_fro(x,ch[k][1]);}
  46     else find_fro(x,ch[k][0]);
  47 }
  48 void find_bac(int x,int k)
  49 {
  50     if(!k)return;
  51     if(num[k]>=x){t2=k;find_bac(x,ch[k][0]);}
  52     else find_bac(x,ch[k][1]);
  53 }
  54 int main()
  55 {
  56     int ans=0;
  57     scanf("%d%d",&n,&ans);
  58     insert(ans,0,root);n--;
  59     while(n--)
  60     {
  61         scanf("%d",&a);
  62         t1=t2=-1; int tmp=0x3f3f3f3f;
  63         find_fro(a,root);
  64         find_bac(a,root);    
  65         if(t1!=-1) tmp=min(tmp,a-num[t1]);
  66         if(t2!=-1) tmp=min(tmp,num[t2]-a);
  67         insert(a,0,root); 
  68         ans+=tmp;                        
  69     }
  70     printf("%d",ans);
  71     return 0;
  72 }

  I‘m here,too!

   

●反转卡片（codevs 1743）

• 一个区间翻转的题，要用到lazy标记,较简单。
• 代码：
• 

   1 #include<cstdio>
   2 #include<iostream>
   3 #include<cstring>
   4 #include<cmath>
   5 #define N 300005
   6 using namespace std;
   7 int n,cnt,rt;
   8 int a[N],c[N][2],fa[N],siz[N],rev[N],num[N];
   9 int read()
  10 {
  11     int x=0,f=1;char ch=getchar();
  12     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
  13     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
  14     return x*f;
  15 }
  16 void update(int k)
  17 {
  18     siz[k]=siz[c[k][0]]+siz[c[k][1]]+1;
  19 }
  20 void pushdown(int k)
  21 {
  22     if(!rev[k]) return;
  23     int l=c[k][0],r=c[k][1];
  24     rev[l]^=1; rev[r]^=1; rev[k]^=1;
  25     swap(c[l][0],c[l][1]);
  26     swap(c[r][0],c[r][1]);
  27 }
  28 int find(int x,int k)
  29 {
  30     pushdown(k);
  31     if(siz[c[k][0]]+1==x) return k;
  32     else if(siz[c[k][0]]+1>x) return find(x,c[k][0]);
  33     else return find(x-siz[c[k][0]]-1,c[k][1]);
  34 }
  35 void rotate(int x,int &k)
  36 {
  37     int y=fa[x],z=fa[y];
  38     int l=c[y][0]!=x,r=l^1;
  39     if(y==k) k=x;
  40     else c[z][c[z][0]!=y]=x;
  41     fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
  42     c[y][l]=c[x][r]; c[x][r]=y;
  43     update(y); update(x);
  44 }
  45 void splay(int x,int &k)
  46 {
  47     int y,z;
  48     while(x!=k)
  49     {
  50         y=fa[x],z=fa[y];
  51         if(y!=k)
  52         {
  53             if(c[z][0]==y^c[y][0]==x) rotate(x,k);
  54             else rotate(y,k);
  55         }
  56         rotate(x,k);
  57     }
  58 }
  59 int split(int k,int len)
  60 {
  61     int x=find(k,rt),y=find(k+len+1,rt);
  62     splay(x,rt); splay(y,c[x][1]);
  63     return c[y][0];
  64 }
  65 void rever(int k,int len)
  66 {
  67     int x=split(k,len);
  68     rev[x]^=1;
  69     swap(c[x][0],c[x][1]);
  70 }
  71 void build(int l,int r,int f)
  72 {
  73     if(l>r) return;
  74     int mid=l+r>>1;
  75     c[f][mid>=f]=mid; 
  76     fa[mid]=f;
  77     num[mid]=a[mid];
  78     build(l,mid-1,mid);
  79     build(mid+1,r,mid);
  80     update(mid);
  81 }
  82 int main()
  83 {
  84     n=read();
  85     a[1]=a[n+2]=0;
  86     for(int i=2;i<=n+1;i++) a[i]=read();
  87     build(1,n+2,0);
  88     rt=n+3>>1;
  89     int len=num[find(2,rt)];
  90     while(len!=1)
  91     {
  92         cnt++;
  93         rever(1,len);
  94         len=num[find(2,rt)];
  95     }
  96     printf("%d",cnt);
  97     return 0;
  98 }

  I‘m here as well!

   

●蚱蜢（codevs 1343）

• Splay维护蚱蜢的位置和区间最大值；
• 用到单点删除和插入；
• （开始题看错了，以为是区间交换，调了半天也没发现代码错误，然后再一看题，……….）
• 代码：
• 

   1 #include<cstdio>
   2 #include<iostream>
   3 #include<cstring>
   4 #include<cmath>
   5 #define N 100050
   6 using namespace std;
   7 int fa[N],c[N][2],a[N],mx[N],siz[N];
   8 int n,m,root;
   9 void pushup(int x)
  10 {
  11     int l=c[x][0],r=c[x][1];
  12     siz[x]=siz[l]+siz[r]+1; mx[x]=max( max(mx[l],mx[r]),a[x]);
  13 }
  14 void rotate(int x,int &k)
  15 {
  16     int y=fa[x],z=fa[y],l=(c[y][0]!=x),r=1^l;
  17     if(y==k) k=x; else c[z][c[z][0]!=y]=x;
  18     fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
  19     c[y][l]=c[x][r]; c[x][r]=y;
  20     pushup(y);pushup(x);
  21 }
  22 void splay(int x,int &k)
  23 {
  24     int y,z;
  25     while(x!=k)
  26     {
  27         y=fa[x]; z=fa[y];
  28         if(y!=k) { if(c[z][0]==y^c[y][0]==x) rotate(x,k); else rotate(y,k); }
  29         rotate(x,k);
  30     }
  31 }
  32 int find(int x,int rt)
  33 {
  34     if(siz[c[rt][0]]+1==x) return rt;
  35     else if(siz[c[rt][0]]+1>x) return find(x,c[rt][0]);
  36     else return find(x-siz[c[rt][0]]-1,c[rt][1]);
  37 }
  38 int split(int a,int b)
  39 {
  40     int x=find(a,root),y=find(b,root);
  41     splay(x,root); splay(y,c[x][1]);
  42     pushup(y); pushup(x);
  43     if(c[y][0]) return c[y][0];
  44     else return y;
  45 }
  46 void build(int l,int r,int last,int &k)
  47 {
  48     if(l>r) return;
  49     k=l+r>>1; fa[k]=last;
  50     if(l==r){mx[k]=a[k]; siz[k]=1;}
  51     build(l,k-1,k,c[k][0]); build(k+1,r,k,c[k][1]); pushup(k);
  52 }
  53 int main()
  54 {
  55     scanf("%d%d",&n,&m);
  56     for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
  57     build(1,n+2,0,root); int zm,st,x,y,z,w; char di;
  58     while(m--)
  59     {
  60         scanf("%d %c %d",&zm,&di,&st);
  61         if(di==‘L‘) x=split(zm-st,zm+1);
  62         else x=split(zm+1,zm+st+2);
  63         printf("%d\n",mx[x]);
  64         
  65         x=split(zm,zm+2); y=fa[x];
  66         c[y][0]=0; fa[x]=0; pushup(y); pushup(fa[y]);
  67         
  68         if(di==‘L‘) y=split(zm-st,zm-st+1); 
  69         else y=split(zm+st+1-1,zm+st+2-1);        
  70         fa[x]=y; c[y][0]=x; 
  71         siz[x]=1; mx[x]=a[x]; pushup(y); pushup(fa[y]);
  72     }
  73     return 0;
  74 }

  Click me here！

   

●GameZ游戏排名系统（codevs 1985）

• 我用的是Splay（权值树）+map（stl），题还不错。
• 单点插入，删除，查询单点信息，查询区间元素；
• 注意（分数会有重复的）
• codevs上是过了，但bzoj上显示Presentation_Error（求助！）
• 代码：
• 

    1 #include<iostream>
    2 #include<cstdio>
    3 #include<string>
    4 #include<map>
    5 #define N 250050
    6 #define inf 4294967305
    7 #define ll long long
    8 using namespace std;
    9 map<string,ll> mp;
   10 ll n,root,id,sz=2,un,c[N][2],fa[N],cnt;
   11 char s[15];
   12 struct info{
   13     ll sz,co;
   14     char na[15];
   15     void nw(ll val)
   16     {
   17         sz=1; co=val; ll i=1;
   18         while(s[i]) na[i-1]=s[i],i++; na[i-1]=0;
   19     }
   20 }fo[N];
   21 void pushup(ll x)
   22 {
   23     ll l=c[x][0],r=c[x][1];
   24     fo[x].sz=fo[l].sz+fo[r].sz+1;
   25 }
   26 void rotate(ll x,ll &k)
   27 {
   28     ll y=fa[x],z=fa[y],l=(c[y][0]!=x),r=1^l;
   29     if(y==k) k=x; else c[z][c[z][0]!=y]=x;
   30     fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
   31     c[y][l]=c[x][r]; c[x][r]=y;
   32     pushup(y);pushup(x);
   33 }
   34 void splay(ll x,ll &k)
   35 {
   36     ll y,z;
   37     while(x!=k)
   38     {
   39         y=fa[x]; z=fa[y];
   40         if(y!=k) { if(c[z][0]==y^c[y][0]==x) rotate(x,k); else rotate(y,k); }
   41         rotate(x,k);
   42     }
   43 }
   44 void insert(ll val,ll x,ll last,ll &rt)
   45 {
   46     if(!rt){rt=x; fo[x].nw(val); fa[x]=last; splay(x,root); return;}
   47     insert(val,x,rt,c[rt][fo[rt].co<val]);
   48 }
   49 void erase()
   50 {
   51     splay(id,root);
   52     ll t1,tt1=c[id][0],t2,tt2=c[id][1];
   53     while(tt1) t1=tt1,tt1=c[t1][1];
   54     while(tt2) t2=tt2,tt2=c[t2][0];
   55     splay(t1,root);
   56     splay(t2,c[t1][1]);
   57     un=c[t2][0];
   58     fa[un]=0;
   59     c[t2][0]=0;
   60     pushup(t2); 
   61     pushup(t1);
   62 }
   63 void ask_rank()
   64 {
   65     if(cnt) printf("\n");
   66     splay(id,root);
   67     printf("%lld",fo[c[id][1]].sz+1-1);
   68     cnt++;
   69 }
   70 ll make_number()
   71 {
   72     ll tot=0,i=1;
   73     while(s[i]) tot=tot*10+s[i]-‘0‘,i++;
   74     return tot;
   75 }
   76 void print_name(ll rt)
   77 {
   78     if(!rt) return;
   79     print_name(c[rt][1]);
   80     printf("%s ",fo[rt].na);
   81     print_name(c[rt][0]);
   82 }
   83 ll find(ll x,ll rt)
   84 {
   85     if(fo[c[rt][1]].sz+1==x) return rt;
   86     else if(fo[c[rt][1]].sz+1>x) return find(x,c[rt][1]);
   87     else return find(x-fo[c[rt][1]].sz-1,c[rt][0]);
   88 }
   89 void ask_name(ll a)
   90 {
   91     if(cnt) printf("\n");
   92     cnt++;
   93     ll b=min(a+1+10,sz);
   94     ll x=find(b,root),y=find(a,root);
   95     splay(x,root);
   96     splay(y,c[x][1]);
   97     pushup(y); pushup(x);
   98     print_name(c[y][0]);
   99      
  100 }
  101 int main()
  102 {
  103     scanf("%lld",&n); ll a;
  104     insert(inf,1,0,root);                       
  105     insert(-1,2,0,root);
  106     while(n--)
  107     {
  108         scanf("%s",s);
  109         id=mp[s+1];
  110         if(s[0]==‘+‘)
  111         {
  112             scanf("%lld",&a);
  113             if(!id) insert(a,id=mp[s+1]=++sz,0,root);
  114             else
  115             {
  116                 erase();
  117                 insert(a,un,0,root);
  118             }
  119         }else
  120         if(‘A‘<=s[1]&&s[1]<=‘Z‘) ask_rank();
  121         else
  122         {
  123             a=make_number();
  124             ask_name(a);
  125         }
  126     }   
  127     return 0;
  128 }

  ......

   

●Splay的一些题