题目链接： https://vjudge.net/problem/26193/origin

　　题目描述： 中文题面.......

　　解题思路： 伸展树， 需要伸展树的模板， 突然发现自己昨天看到的模板不是太好， 现在又新找了一个，  很简练， 自己将模板的实现从头到尾看了一遍， 觉得数组实现的实在是非常的巧妙， 然后自己照着敲了一遍， 边敲边看， 崩掉了.....肯定是哪里手残了， 没有必要浪费时间去改了， 有那时间不如看点别的

　　代码： 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long LL;const int Max = 100010;const int INF = 0x3f3f3f3f;struct SplayTree{ int num[Max],pre[Max],next[Max][2],key[Max]; int root,Size; void PushUp(int x) //向上更新，计算以自己为根节点的树中节点的个数 { num[x] = num[next[x][0]] + num[next[x][1]]+1; } void Rotate(int x,int kind)//伸展操作 { int y = pre[x]; int z = pre[y]; next[y][!kind] = next[x][kind]; pre[next[x][kind]] = y; next[z][next[z][1]==y] = x; pre[x] = z; next[x][kind] = y; pre[y] = x; PushUp(y); PushUp(x); } void Splay(int x,int goal) { if(x!=goal) { while(pre[x]!=goal) { if(next[pre[x]][0] == x) { Rotate(x,1); } else Rotate(x,0); } } if(!goal) root = x; } void NewNode(int &x,int y,int val) { x = ++Size; num[x] = 1; pre[x] = y; next[x][0] = next[x][1] = 0; key[x] = val; next[y][val>key[y]] = x; } void Insert(int val)//插入节点 { int x,y; for(x = root,y = 0;x;x = next[x][val>key[x]]) { y = x; num[x]++; } NewNode(x,y,val); Splay(x,0); } int Search(int val) //查询比小于等于val的节点的位置 { int res,x; for(res = 0, x = root;x;x = next[x][val>key[x]]) { if(key[x] >= val && key[res] >= key[x]) { res = x; } } return res; } int Select(int k)//查找第k大。 { int x = root; k = num[root]-k; for(x = root; num[next[x][0]]+1!=k;) { if(num[next[x][0]]+1
               
                = Mi) { Tr.Insert(data-Mi+diff); } } else if(op[0] == 'A') { diff-=data; } else if(op[0] == 'S') { diff += data; Tr.Splay(Tr.Search(diff),0); ans+=Tr.num[Tr.next[Tr.root][0]]; Tr.num[Tr.root] -= Tr.num[Tr.next[Tr.root][0]]; Tr.next[Tr.root][0] = 0; } else { if(data>=Tr.num[Tr.root]) { printf("-1\n"); } else { printf("%d\n",Tr.Select(data)+Mi-diff); } } } printf("%d\n",ans); } return 0;}
               
              
             
            
           
          
         
        
       
      

　　思考： 自己数据结构的知识是真的需要好好的加强， 然后自己应该照着组合数学的题单搞一搞了