缺少删除，见下一篇中的treap平衡树

特点：左大右小

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define M 99999using namespace std;int lc[M],rc[M],size[M],key[M],f[M],tot=0;int n,m;int root=1;int add(int v){ tot++; size[tot]=1; key[tot]=v; return tot;}void insert(int &t,int v){ if(!t) t=add(v); else if(v
            
             k-1) return askmin(lc[t],k); else return askmin(rc[t],k-size[lc[t]]-1);//当前点是第size[lc[t]]+1大的值 }//与下面while版 askmin()等价 */int askmin(int t,int k)//查找第k小的数 { int b=0; while(1){ if(size[lc[t]]==k-(1+b)) return key[t]; if(size[lc[t]]>k-1) t=lc[t]; else { b+=size[lc[t]]+1;// b累加 t=rc[t]; } } }/*int askxth(int t,int x)//查询x的排名 { if(key[t]==x) return size[lc[t]]+1; if(key[t]> x) return askxth(lc[t],x); if(key[t]< x) return askxth(rc[t],x)+size[lc[t]]+1;}//下面是 while 版 */int askxth(int t,int x)//查询x的排名 { int b=0; while(1) { if(key[t]==x) break; if(key[t]>x) t=lc[t]; if(key[t]
             
              =x&&(key[lc[t]]