POJ 2985 Treap平衡树（求第k大的元素） - c++编程基础

这题也可以用树状数组做，而且树状数组姿势更加优美，代码更加少，不过这个Treap树就是求第K大元素的专家……所以速度比较快！

这个也是从那本红书上拿的模板……自己找了资料百度了好久，才理解这个Treap基本的知识，要是自己写真的得写到什么时候啊！！！

然后输入的时候是写n-k+1反着找的，就是这里又浪费了好多时间debug，唉……

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 440004 #define MN 1008 #define INF 100000007 #define eps 1e-7 using namespace std; typedef long long LL; typedef unsigned long long ULL; struct Treap { int root,treapCnt,key[MM],priority[MM],childs[MM][2],cnt[MM],size[MM]; Treap() { root=0; treapCnt=1; priority[0]=INF; size[0]=0; } void update(int x) { size[x]=size[childs[x][0]]+cnt[x]+size[childs[x][1]]; } void rotate(int &x,int t) { int y=childs[x][t]; childs[x][t]=childs[y][1-t]; childs[y][1-t]=x; update(x); update(y); x=y; } void _insert(int &x,int k) { if(x) { if(key[x]==k) cnt[x]++; else { int t=key[x]
                
                 1) cnt[x]--; else { if(childs[x][0]==0&&childs[x][1]==0) { x=0; return ; } int t=priority[childs[x][0]]>priority[childs[x][1]]; rotate(x,t); _erase(x,k); } } else _erase(childs[x][key[x]