解题关键：无旋treap模板。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 500001using namespace std;typedef long long ll;int size[maxn],ch[maxn][2],rnd[maxn],val[maxn];int ncnt,n,x,y,z,rt;inline void pushup(int x){ size[x]=1+size[ch[x][0]]+size[ch[x][1]];}inline int new_node(int x){ size[++ncnt]=1; val[ncnt]=x; rnd[ncnt]=rand(); return ncnt;}//核心int merge(int A,int B){ if(!A||!B) return A+B; if(rnd[A]