记录编号	424045	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	4.125 s
提交时间	2017-07-12 19:53:34	内存使用	3.36 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define size(x) ((x)? (x->s):(0))
const int MAXN = 50005*8;
const int inf =0x7fffffff;


inline int read(){
	int s=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*f;
}
 
 
struct node{
	int v,r,s;
	node *ch[2];
	node(int x){
		v=x;
		r=rand();
		s=1;
		ch[0]=ch[1]=NULL;
	}
	int cmp(int x)const{
		if(v==x)return -1;
		return x<v?0:1;
	}
	int Maintain(){
		s=size(ch[0])+size(ch[1])+1;
	}
}*root[MAXN]={NULL};
 
int n,m,a[MAXN];
 
inline void rotate(node* &o,int d){
	node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->Maintain();
	k->Maintain();
	o=k;
}
 
void insert(node* &o,int x){
	if(o==NULL)o=new node(x);
	else{
		int d=x<o->v?0:1;
		insert(o->ch[d],x);
		if(o->ch[d]->r > o-> r)
			rotate(o,d^1);
	}
	o->Maintain();
}
 
void del(node* &o,int x){
	if(o==NULL)return;
	int d=o->cmp(x);
	if(d==-1){
		node *tmp=o;
		if(o->ch[0]!=NULL&&o->ch[1]!=NULL){
			int k=o->ch[0]->r > o->ch[1]->r ?1:0;
			rotate(o,k);
			del(o->ch[k],x);
		}
		else{
			if(o->ch[0]==NULL)o=o->ch[1];
			else o=o->ch[0];
			delete tmp;
			tmp=NULL;
		}
	}
	else del(o->ch[d],x);
	if(o!=NULL)o->Maintain();
}
 
void change(int o,int l,int r){for(int i=l;i<=r;i++)insert(root[o],a[i]);}
 
void build(int o,int l,int r){
	change(o,l,r);
	if(l==r)return;
	int m=l+r>>1;
	build(o*2,l,m);
	build(o*2+1,m+1,r);
}
 
void remove(int o,int l,int r,int x,int y){
	del(root[o],y);
	if(l==r)return;
	int m=l+r>>1;
	if(x<=m)remove(o*2,l,m,x,y);
	else remove(o*2+1,m+1,r,x,y);
}
 
void updata(int o,int l,int r,int x,int y){
	insert(root[o],y);
	if(l==r)return;
	int m=l+r>>1;
	if(x<=m)updata(o*2,l,m,x,y);
	else updata(o*2+1,m+1,r,x,y);
}
 
inline int rank(node *o,int x){
	int ans=0;
	while(o){
		if(o->v<x)ans+=size(o->ch[0])+1,o=o->ch[1];
		else o=o->ch[0];
	}
	return ans;
}
 
inline int rank(int o,int l,int r,int x,int y,int query){
	if(x<=l&&r<=y)return rank(root[o],query);
	int m=l+r>>1,ans=0;
	if(x<=m)ans+=rank(o*2,l,m,x,y,query);
	if(m<y)ans+=rank(o*2+1,m+1,r,x,y,query);
	return ans;
}
 
inline int kth(int x,int y,int z){
	int l=0,r=inf,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(rank(1,1,n,x,y,mid)<z)l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
 
int main(){
#define LOCAL
#ifdef LOCAL
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op=read(),x=read(),y=read(),z;
		if(op==1){
			z=read();
			printf("%d\n",rank(1,1,n,x,y,z)+1);
		}
		if(op==2){
			z=read();
			printf("%d\n",kth(x,y,z));
		}
		if(op==3){
			remove(1,1,n,x,a[x]);
			a[x]=y;
			updata(1,1,n,x,y);
		}
		if(op==4){
			z=read();
			printf("%d\n",kth(x,y,rank(1,1,n,x,y,z)));
		}
		if(op==5){
			z=read();
			printf("%d\n",kth(x,y,rank(1,1,n,x,y,z+1)+1));
		}
	}
	return 0;
}