fhq treap

非旋treap

fhq是天才! 先放板子

# include <iostream>
# include <cstdlib>
using namespace std;
struct node{
    int val,rnd,l,r,size;
}tree[100010];int top,root;
void pushup(int x){
    tree[x].size = tree[tree[x].l].size+tree[tree[x].r].size+1;
}
int newnode(int x){
    tree[++top].val = x;tree[top].size  = 1;tree[top].rnd = rand();
    return top;
}
int merge(int x,int y){//x<y
    if(!x||!y)return x+y;//已经空了
    if(tree[x].rnd<tree[y].rnd){
        tree[x].r = merge(tree[x].r,y);
        pushup(x);return x;
    }else {
        tree[y].l = merge(x,tree[y].l);
        pushup(y);return y;
    }
}
void split(int now,int k,int &x,int &y){//以x为权值分为两棵树
    if(!now) x=y=0;//
    else {
        if(tree[now].val<=k)
        x = now,split(tree[now].r,k,tree[now].r,y);
        else 
            y = now,split(tree[now].l,k,x,tree[now].l);
        pushup(now);
    }
}
int kth(int now,int k){
    while(true){
        if(k<=tree[tree[now].l].size){
            now = tree[now].l;
        }else {
        	if(k==tree[tree[now].l].size+1)return now;
        	else{
         	   k-=tree[tree[now].l].size+1;
          	   now = tree[now].r;
        	}
        }
    }
}
int main(){
    srand(19260817);
    int T,op,x,y,z,a,b;cin>>T;
    while(T--){
    	cin>>op>>a;
        if(op==1){
            split(root,a,x,y);
            root = merge(merge(x,newnode(a)),y);
        }else if(op==2){
            split(root,a,x,z);split(x,a-1,x,y);
            y = merge(tree[y].l,tree[y].r);
            root = merge(merge(x,y),z);
        }else if(op==3){
            split(root,a-1,x,y);
            cout<<tree[x].size+1<<endl;
            root = merge(x,y);
        }else if(op==4){
            cout<<tree[kth(root,a)].val<<endl;
        }else if(op==5){
            split(root,a-1,x,y);
            cout<<tree[kth(x,tree[x].size)].val<<endl;
            root = merge(x,y);
        }else if(op==6){
            split(root,a,x,y);
            cout<<tree[kth(y,1)].val<<endl;
            root = merge(x,y);
        }
    }
    return 0;
}