Treap树（模板）

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define inf 300000030
#define M 100100 
using namespace std;

int l[M],r[M],v[M],size[M],rnd[M],ct[M];
int sz,ss;

void update(int p){
    size[p]=size[l[p]]+size[r[p]]+ct[p];
}

void lturn(int &k){
    int t=r[k];
    r[k]=l[t];
    l[t]=k;
    size[t]=size[k];
    update(k);
    k=t;
}

void rturn(int &k){
    int t=l[k];
    l[k]=r[t];
    r[t]=k;
    size[t]=size[k];
    update(k);
    k=t;
}

void ins(int &p,int x){
    if(p==0){
        p=++sz;
        size[p]=ct[p]=1,v[p]=x,rnd[p]=rand();
        return;
    }
    size[p]++;
    if(v[p]==x) ct[p]++;
    else 
		if(x>v[p]){
	        ins(r[p],x);
	        if(rnd[r[p]]<rnd[p]) lturn(p);
	    }
	    else{
	        ins(l[p],x);
	        if(rnd[l[p]]<rnd[p]) rturn(p);
	    }
}
void del(int &p,int x){
    if(p==0) return;
    if(v[p]==x){
        if(ct[p]>1) ct[p]--,size[p]--;
        else{
            if(l[p]==0||r[p]==0) p=l[p]+r[p];
            else 
				if(rnd[l[p]]<rnd[r[p]]) rturn(p),del(p,x);
            	else lturn(p),del(p,x); 
        }
    }
    else
		if(x>v[p]) size[p]--,del(r[p],x);
    	else size[p]--,del(l[p],x);
}

int query1(int p,int x){
    if(p==0) return 0;
    if(v[p]==x) return size[l[p]]+1;
    if(x>v[p]) return size[l[p]]+ct[p]+query1(r[p],x);
    else return query1(l[p],x);
}

int query2(int p,int x){
    if(p==0) return 0;
    if(x<=size[l[p]]) return query2(l[p],x);
    x-=size[l[p]];
    if(x<=ct[p]) return v[p];
    x-=ct[p];
    return query2(r[p],x);
 }
 
 int findfront(int p,int x){
    if(p==0) return -inf;
    if(v[p]<x) return max(v[p],findfront(r[p],x));
    else if (v[p]>=x) return findfront(l[p],x);
}

int findback(int p,int x){
    if(p==0) return inf;
    if(v[p]<=x) return findback(r[p],x);
    else return min(v[p],findback(l[p],x));
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    {
        int flag,x;
        scanf("%d%d",&flag,&x);
        if (flag==1) ins(ss,x);
        if (flag==2) del(ss,x);
        if (flag==3) printf("%d\n",query1(ss,x));
        if (flag==4) printf("%d\n",query2(ss,x)); 
        if (flag==5) printf("%d\n",findfront(ss,x));
        if (flag==6) printf("%d\n",findback(ss,x));
    }
    return 0;
}