Memphis's Blog

/*
	Treap[Merge,Split]
	by Memphis
*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
#define maxn 2000005
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)

struct Treap{
	Treap *l,*r;
	int fix,key,size;
	Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(1){}
	
	inline void updata(){
		size=1+(l?l->size:0)+(r?r->size:0);
	}
}*root;
typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 

inline int Size(Treap *x){return x?x->size:0;}//这样求size可以防止访问空指针 

Treap *Merge(Treap *A,Treap *B){//合并操作 
	if(!A)return B;
	if(!B)return A;
	if(A->fix<B->fix){
		A->r=Merge(A->r,B);
		A->updata();
		return A;
	}else{
		B->l=Merge(A,B->l);
		B->updata();
		return B;
	}
}

Droot Split(Treap *x,int k){//拆分操作 
	if(!x)return Droot(NULL,NULL);
	Droot y;
	if(Size(x->l)>=k){
		y=Split(x->l,k);
		x->l=y.second;
		x->updata();
		y.second=x;
	}else{
		y=Split(x->r,k-Size(x->l)-1);
		x->r=y.first;
		x->updata();
		y.first=x;
	}
	return y;
}

Treap *Build(int *a){//建造操作 
	static Treap *stack[maxn],*x,*last;
	int p=0;
	rep(i,1,a[0]){
		x=new Treap(a[i]);
		last=NULL;
		while(p && stack[p]->fix>x->fix){
			stack[p]->updata();
			last=stack[p];
			stack[p--]=NULL;
		}
		if(p) stack[p]->r=x;
		x->l=last;
		stack[++p]=x;
	}
	while(p) stack[p--]->updata();
	return stack[1];
}

int Findkth(int k){//查找第K小 
	Droot x=Split(root,k-1);
	Droot y=Split(x.second,1);
	Treap *ans=y.first;
	root=Merge(Merge(x.first,ans),y.second);
	return ans->key;
}

int Getkth(Treap *x,int v){//询问一个数是第几大 
	if(!x)return 0;
	return v<x->key?Getkth(x->l,v):Getkth(x->r,v)+Size(x->l)+1;
}

void Insert(int v){//插入操作 
	int k=Getkth(root,v);
	Droot x=Split(root,k);
	Treap *n=new Treap(v);
	root=Merge(Merge(x.first,n),x.second);
}

void Delete(int k){//删除操作 
	Droot x=Split(root,k-1);
	Droot y=Split(x.second,1);
	root=Merge(x.first,y.second);
}

int a[maxn],M,x,y;

int main(){
	freopen("bst.in","r",stdin);
	freopen("bst.out","w",stdout);
	
	scanf("%d",a);
	rep(i,1,a[0]) scanf("%d",a+i);
	sort(a+1,a+1+a[0]);
	root=Build(a);
	
	scanf("%d",&M);
	while(M--){
		char ch=getchar();
		while(ch!='Q' && ch!='A' && ch!='D') ch=getchar();
		scanf("%d",&x);
		if(ch=='Q') printf("%d\n",Findkth(x));
		if(ch=='A') Insert(x);
		if(ch=='D') Delete(x);
	}
}	

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 5000005
#define inf 0x7f7f7f7f
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
 
int N,M,x;
 
inline int sqr(const int x){return x*x;}//平方
int power2(int x){//找到第一个大于等于x的二的整次幂
    int ans=1;
    for(;ans<x;ans<<=1);
    return ans;
}
 
struct SQRT{//二的整次幂的开根上取和开根下取
    int upper,lower;
}Sqrt[maxn];
 
/////////////////* van Emde Boas tree
 
int cluster_cnt,max_low,min_low,offset,succ_cluster,pred_cluster,first_cluster,summary_max;
 
struct vEB_tree;
vEB_tree *cluster[maxn];
 
struct vEB_tree{//以下部分解释详见《算法导论》
    int p,u,Min,Max;
    vEB_tree *summary;
     
    inline int high(int x){return x/Sqrt[u].lower;}
    inline int low(int x){return x%Sqrt[u].lower;}
    inline int index(int x,int y){return x*Sqrt[u].lower+y;}
    vEB_tree(){}
     
    vEB_tree(int n):u(n){
        p=cluster_cnt;
        if(n>2){
            cluster_cnt+=Sqrt[n].upper;
            Min=cluster_cnt-1;
            rep(i,p,Min)
                cluster[i]=new vEB_tree(Sqrt[n].lower);
            summary=new vEB_tree(Sqrt[n].upper);
        }
        Min=Max=inf;
    }
     
    int vEB_tree_Minimum(){return Min;}
    int vEB_tree_Maximum(){return Max;}
     
    bool vEB_tree_Member(int x){
        if(x==Min || x==Max) return true;
        if(u==2) return false;
        return cluster[p+high(x)]-> vEB_tree_Member(low(x));
    }
     
    int vEB_tree_Successor(int x){
        if(u==2){
            if(x==0 && Max==1) return 1;
            return inf;
        }
        if(Min<=N && x<Min) return Min;
        max_low=cluster[p+high(x)]-> vEB_tree_Maximum();
        if(max_low<=N && low(x)<max_low){
            offset=cluster[p+high(x)]-> vEB_tree_Successor(low(x));
            return index(high(x),offset);
        }
        succ_cluster=summary-> vEB_tree_Successor(high(x));
        if(succ_cluster>N) return inf;
        offset=cluster[p+succ_cluster]-> vEB_tree_Minimum();
        return index(succ_cluster,offset);
    }
     
    int vEB_tree_Predecessor(int x){
        if(u==2){
            if(x==1 && Min==0) return 0;
            return inf;
        }
        if(Max<=N && x>Max) return Max;
        min_low=cluster[p+high(x)]-> vEB_tree_Minimum();
        if(min_low<=N && low(x)>min_low){
            offset=cluster[p+high(x)]-> vEB_tree_Predecessor(low(x));
            return index(high(x),offset);
        }
        pred_cluster=summary-> vEB_tree_Predecessor(high(x));
        if(pred_cluster>N){
            if(Min<=N && x>Min) return Min;
            return inf;
        }
        offset=cluster[p+pred_cluster]-> vEB_tree_Maximum();
        return index(pred_cluster,offset);
    }
     
    inline void vEB_empty_tree_Insert(int x){Min=Max=x;}
     
    void vEB_tree_Insert(int x){
        if(Min>N) vEB_empty_tree_Insert(x);
        else{
            if(x<Min) swap(x,Min);
            if(u>2){
                if(cluster[p+high(x)]-> vEB_tree_Minimum()>N){
                    summary-> vEB_tree_Insert(high(x));
                    cluster[p+high(x)]-> vEB_empty_tree_Insert(low(x));
                }else
                    cluster[p+high(x)]-> vEB_tree_Insert(low(x));
            }
            if(x>Max) Max=x;
        }
    }
     
    void vEB_tree_Delete(int x){
        if(Min==Max) Min=Max=inf;
        else{
            if(u==2){
                if(x==0) Min=1;
                else Min=0;
                Max=Min;
            }else{
                if(x==Min){
                    first_cluster=summary-> vEB_tree_Minimum();
                    x=index(first_cluster,cluster[p+first_cluster]-> vEB_tree_Minimum());
                    Min=x;
                }
                cluster[p+high(x)]-> vEB_tree_Delete(low(x));
                if(cluster[p+high(x)]-> vEB_tree_Minimum()>N){
                    summary-> vEB_tree_Delete(high(x));
                    if(x==Max){
                        summary_max=summary-> vEB_tree_Maximum();
                        if(summary_max>N) Max=Min;
                        else
                            Max=index(summary_max,cluster[p+summary_max]-> vEB_tree_Maximum());
                    }
                }else
                    if(x==Max)
                        Max=index(high(x),cluster[p+high(x)]-> vEB_tree_Maximum());
            }
        }
    }
     
}*root;
 
void Initialization(int n){//初始化
    for(int i=0;(1<<i)<=n;++i){
        Sqrt[1<<i].lower=1<<i/2;
        Sqrt[1<<i].upper=1<<i/2+i%2;
    }
 
    root=new vEB_tree(n);//构造vEB tree
}
 
int main(){
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
 
    scanf("%d",&N);
 
    Initialization(power2(N));
     
    rep(i,1,N){
        scanf("%d",&x);
        root-> vEB_tree_Insert(x-1);
    }
     
    int opt,x;
    rep(i,1,N){
        scanf("%d%d",&opt,&x);
         
        if(opt==1) root-> vEB_tree_Insert(x-1);
        if(opt==2) root-> vEB_tree_Delete(x-1);
        if(opt==3) printf("%d\n",root-> vEB_tree_Predecessor(x-1)+1);
        if(opt==4) printf("%d\n",root-> vEB_tree_Successor(x-1)+1);
    }
}