无旋treap

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define P pair<int,int>
#define ls(x) T[x].ls
#define rs(x) T[x].rs
using namespace std;
struct Treenode
{
    int val,ls,rs,size;
    int rnd;
}T[100010];
int cnt,n,rt;
int ran()
{
    static int seed=20172101;
    seed+=(seed<<2)+1;
    return seed;
}
void update(int a)
{
    T[a].size=T[ls(a)].size+T[rs(a)].size+1;
}
int merge(int a,int b) //maxa<minnb
{
    if(a==0)return b;
    if(b==0)return a;
    if(T[a].rnd<T[b].rnd) {T[a].rs=merge(T[a].rs,b);update(a);return a;}
    else {T[b].ls=merge(a,T[b].ls);update(b);return b;}
}
P split(int a,int n)
{
    if(n==0) return make_pair(0,a);
    int L=ls(a),R=rs(a);
    if(n==T[L].size) {T[a].ls=0;update(a);return make_pair(L,a);}
    if(n==T[L].size+1) {T[a].rs=0;update(a);return make_pair(a,R);}
    if(n<T[L].size)
    {
        P tmp=split(L,n);
        T[a].ls=tmp.second;update(a);return make_pair(tmp.first,a);
    }
    P tmp=split(R,n-T[L].size-1);
    T[a].rs=tmp.first;update(a);return make_pair(a,tmp.second);
}
int rank(int x,int rt)
{
    int ans=0,tp=2147483233;
    while(rt)
    {
        if(T[rt].val==x) tp=min(tp,ans+T[ls(rt)].size+1);
        if(T[rt].val<x) {ans+=T[ls(rt)].size+1;rt=rs(rt);}
        else rt=ls(rt);
    }
    return tp==2147483233?ans:tp;
}
int find(int x,int rt)
{
    while(1)
    {
       if(T[ls(rt)].size==x-1) return T[rt].val;
       if(T[ls(rt)].size>x-1) rt=ls(rt);
       else {x=x-T[ls(rt)].size-1;rt=rs(rt);}
    }
}
int pre(int x,int k)
{
    int ans=-(int)1e9;
    while(k)
    {
        if(T[k].val<x) {ans=max(ans,T[k].val);k=rs(k);}
        else k=ls(k);
    }
    return ans;
}
int suf(int x,int k)
{
    int ans=(int)1e9;
    while(k)
    {
        if(T[k].val>x) {ans=min(ans,T[k].val);k=ls(k);}
        else k=rs(k);    
    }    
    return ans;
}
int add(int x)
{
    int k=rank(x,rt);
    P tmp=split(rt,k);
    T[++cnt].val=x;
    T[cnt].rnd=ran();
    T[cnt].size=1;
    rt=merge(tmp.first,cnt);
    rt=merge(rt,tmp.second);
}
int del(int x)
{
    int k=rank(x,rt);
    P t1=split(rt,k);
    P t2=split(t1.first,k-1);
    rt=merge(t2.first,t1.second);
}
int main()
{
    scanf("%d",&n);
    rt=0;
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
            add(x);
        if(opt==2)
            del(x);
        if(opt==3)
            printf("%d
",rank(x,rt));
        if(opt==4)
            printf("%d
",find(x,rt));
        if(opt==5)
            printf("%d
",pre(x,rt));
        if(opt==6)
            printf("%d
",suf(x,rt));
    }
}