记录编号	214762	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.152 s
提交时间	2015-12-17 20:30:17	内存使用	1.07 MiB

// data structure  = = eating 

#define lson l,mid,t
#define rson mid+1,r,t|1

#define MAXN 50010UL

#include <cstdio>
#include <cstdlib>

struct Node{
	Node *left,*right;
	int fix,val,size;
	Node(){
		fix=rand();
		size=1;
		left=right=NULL;
		return;
	}
}*root[MAXN*3];

int n,m,seq[MAXN],pos,posl,posr,before_val,update_val,query_val;

inline int in(){
	int x=0,c=getchar();
	bool flag=false;
	while(c<'0'||c>'9'){
		if(c=='-') flag=true;
		c=getchar();	
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

inline void Update(Node *&p){
	if(p==NULL) return;
	p->size=1;
	if(p->left!=NULL) p->size+=p->left->size;
	if(p->right!=NULL) p->size+=p->right->size;;
	return;
}

inline void Lturn(Node *&a){
	Node *b=a->right;
	a->right=b->left;
	b->left=a;a=b;
	Update(b->left);
	return;
}

inline void Rturn(Node *&a){
	Node *b=a->left;
	a->left=b->right;
	b->right=a;a=b;
	Update(b->right);
	return;
}

inline void Insert(Node *&p,int val){
	if(p==NULL){
		p=new Node();
		p->val=val;
	}
	else if(val<=p->val){
		Insert(p->left,val);
		if(p->left->fix<p->fix) Rturn(p);
	}
	else{
		Insert(p->right,val);
		if(p->right->fix<p->fix) Lturn(p);
	}
	Update(p);
	return;
}

inline void Delete(Node *&p,int val){
	if(p->val==val){
		if(p->left==NULL||p->right==NULL){
			Node *t=p;
			if(p->left!=NULL) p=p->left;
			else p=p->right;
			delete t;
		}
		else if(p->left->fix<p->right->fix) Rturn(p),Delete(p->right,val);
		else Lturn(p),Delete(p->left,val);
	}
	else if(val<p->val) Delete(p->left,val);
	else Delete(p->right,val);
	Update(p);
	return;
}

inline void Build(int l,int r,int rt){
	for(int i=l;i<=r;i++) Insert(root[rt],seq[i]);
	if(l==r) return;
	int mid=(l+r)>>1,t=rt<<1;
	Build(lson);
	Build(rson);
	return;
}

inline int Find_How_Many_Smaller(Node *p,int val){
	if(p==NULL) return 0L;
	if(p->val<val){
		int Ans=Find_How_Many_Smaller(p->right,val)+1;
		if(p->left!=NULL) Ans+=p->left->size;
		return Ans;
	}
	else return Find_How_Many_Smaller(p->left,val);
}

inline int Find_First_Smaller(Node *p,int val){
	if(p==NULL) return -1;
	if(p->val<val){
		int k=Find_First_Smaller(p->right,val);
		if(k!=-1) return k;
		else return p->val;
	}
	return Find_First_Smaller(p->left,val);
}

inline int Find_First_Bigger(Node *p,int val){
	if(p==NULL) return -1;
	if(p->val>val){
		int k=Find_First_Bigger(p->left,val);
		if(k!=-1) return k;
		else return p->val;		
	}
	return Find_First_Bigger(p->right,val);
}

inline int Aft(int l,int r,int rt){
	if(posl<=l&&posr>=r)
		return Find_First_Bigger(root[rt],query_val);
	int mid=(l+r)>>1,t=rt<<1,k,Ans=-1;
	if(posl<=mid){
		k=Aft(lson);
		if(k!=-1) Ans=k;
	}
	if(posr>mid){
		k=Aft(rson);
		if(Ans==-1||k!=-1&&Ans!=-1&&k<Ans) Ans=k;
	}
	return Ans;
}

inline int Pre(int l,int r,int rt){
	if(posl<=l&&posr>=r)
		return Find_First_Smaller(root[rt],query_val);
	int mid=(l+r)>>1,t=rt<<1,k,Ans=-1;
	if(posl<=mid){
		k=Pre(lson);
		if(k!=-1) Ans=k;
	}
	if(posr>mid){
		k=Pre(rson);
		if(Ans==-1||k!=-1&&Ans!=-1&&k>Ans) Ans=k;
	}
	return Ans;
}

inline int QueryRank(int l,int r,int rt){
	if(posl<=l&&posr>=r)
		return Find_How_Many_Smaller(root[rt],query_val);
	int mid=(l+r)>>1,t=rt<<1,Ans=0;
	if(posl<=mid)
		Ans+=QueryRank(lson);
	if(posr>mid)
		Ans+=QueryRank(rson);
	return Ans;
}

inline void Update(int l,int r,int rt){
	Delete(root[rt],before_val);
	Insert(root[rt],update_val);
	if(l==r) return;
	int mid=(l+r)>>1,t=rt<<1;
	if(pos<=mid) Update(lson);
	else Update(rson);
	return;
}

int main(){
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	n=in(),m=in();
	for(int i=1;i<=n;i++) seq[i]=in();
	Build(1,n,1);
	for(int i=1,op,k;i<=m;i++){
		op=in();
		switch(op){
			case 1:{
				posl=in();
				posr=in();
				query_val=in();
				printf("%d\n",QueryRank(1,n,1)+1);
				break;
			}
			case 2:{
				posl=in();
				posr=in();
				k=in();
				int Ans=0,L=0,R=(int)1e9,ranking;
				while(L<=R){
					query_val=(L+R)>>1;
					ranking=QueryRank(1,n,1)+1;
					if(ranking<=k) L=query_val+1,Ans=query_val;
					else R=query_val-1;
				}
				printf("%d\n",Ans);
				break;
			}
			case 3:{
				pos=in();
				update_val=in();
				before_val=seq[pos];
				seq[pos]=update_val;
				Update(1,n,1);
				break;
			}
			case 4:{
				posl=in();
				posr=in();
				query_val=in();
				printf("%d\n",Pre(1,n,1));
				break;
			}
			case 5:{
				posl=in();
				posr=in();
				query_val=in();
				printf("%d\n",Aft(1,n,1));
				break;
			}
		}
	}
	return 0;
}