//Treap fhq版(不旋转) //所有操作依靠split()(分离)和merge()(合并)完成 //可支持区间操作和可持久化 比普通Treap更通用 //所有Treap中序遍历均为递增序列 #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,cnt,size,root,x,y,z;//x为小Treap的根节点 y为中Treap的根节点 z为大Treap的根节点 root为总Treap的根节点 int son[100001][2],siz[100001],val[100001],rd[100001];//左右儿子，子树大小+自己大小，点值，随机权值 int new_node(int m)//建立新节点 { siz[++size]=1; val[size]=m; rd[size]=rand(); return size;}void update(int now){ siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;}void split(int now,int k,int &a,int &b){ if(!now) { a=b=0; return; } if(val[now]<=k) a=now,split(son[now][1],k,son[now][1],b); //将此节点及其左子树接到小Treap上，并遍历此节点的右节点 else b=now,split(son[now][0],k,a,son[now][0]); //将此节点及其右子树接到大Treap上，并遍历此节点的左节点 update(now);}int merge(int a,int b){ if(!a||!b) return a+b; if(rd[a]