记录编号	424085	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	5.124 s
提交时间	2017-07-12 20:24:57	内存使用	1.27 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define inf 1e8
#define size(a) ((a!=NULL)?(a)->size:0)
using namespace std;
int n,m,a[50005];
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
 
struct node{
	int key,num,size,tot;
	node *ch[2];
	node(int x=0){
		key=rand();num=x;size=tot=1;
		memset(ch,0,sizeof ch);
	}
	void* operator new(size_t);
	void operator delete(void  *p);
}*root[200005],*C,*M;
 
vector<node*> q;
 
void* node :: operator new(size_t){
	node *p;
	if(!q.empty()){
		p=q.back();
		q.pop_back();
	}
	else {if(C==M){
			C=new node[1<<10];
			M=C+(1<<10);
		}p=C++;
	}
	return p;
}
 
void node :: operator delete(void *p){
	q.push_back((node*)p);
}
 
void pushup(node *now){
	if(!now) return ;
	now->size=size(now->ch[0])+size(now->ch[1])+now->tot;
}
 
void rot(node *&now,int wh){
	node *t=now->ch[wh];
	now->ch[wh]=t->ch[wh^1];
	t->ch[wh^1]=now;
	pushup(now);pushup(t);
	now=t;
}
 
void insert(node *&now,int x){
	if(!now){
		now=new node(x);
		return ;
	}
	if(now->num==x){now->tot++;now->size++;return;}
	int wh=now->num<x;
	insert(now->ch[wh],x);
	pushup(now); 
	if(now->ch[wh]->key<now->key) rot(now,wh);
}
 
void del(node *&now,int x){
	if(!now) return;
	if(now->num==x){
		if(now->tot>1){now->tot--;now->size--;return;}
		else if(now->ch[0]==NULL&&now->ch[1]==NULL){delete now;now=NULL;return;}
		else if(now->ch[0]==NULL){
			node *t=now;
			now=now->ch[1];
			delete t; t=NULL;
		}
		else if(now->ch[1]==NULL){
			node *t=now;
			now=now->ch[0];
			delete t; t=NULL;
		}
		else{
			int wh=now->ch[0]->key>now->ch[1]->key;
			rot(now,wh); del(now,x);
		}
	}
	else{
		if(now->num<x) del(now->ch[1],x);
		else del(now->ch[0],x);
	}
	if(now) pushup(now);
}
 
int rank(node *now,int x){
	int ans=0;
	while(now){
		if(now->num<x){
			ans+=size(now->ch[0])+now->tot;
			now=now->ch[1];
		}
		else if(now->num==x){ans+=size(now->ch[0]);break;}
		else now=now->ch[0];
	}
	return ans;
}
 
void build(int now,int l,int r,int pos,int x){
	insert(root[now],x);
	if(l==r) return ;
	int mid=(l+r)/2;
	if(pos<=mid) build(now<<1,l,mid,pos,x);
	else build(now<<1|1,mid+1,r,pos,x);
}
 
int getrank(int now,int l,int r,int x,int y,int pos){
	int ans=0;
	if(l>=x&&r<=y){
		ans+=rank(root[now],pos);
		return ans;
	}
	int mid=(l+r)/2;
	if(x<=mid) ans+=getrank(now<<1,l,mid,x,y,pos);
	if(y>mid) ans+=getrank(now<<1|1,mid+1,r,x,y,pos);
	return ans;
}
 
int getkth(int x,int y,int z){
	int l=0,r=inf,mid; z--;
    while(l+1<r){
        mid=(l+r)/2;
        if(getrank(1,1,n,x,y,mid)<=z) l=mid;
        else r=mid;
    }
    if(getrank(1,1,n,x,y,r)>z) return l;
    return r;
}
 
void update(int now,int l,int r,int pos,int x){
	del(root[now],a[pos]);
	insert(root[now],x);
	if(l==r) return ;
	int mid=(l+r)/2;
	if(pos<=mid) update(now<<1,l,mid,pos,x);
	else update(now<<1|1,mid+1,r,pos,x);
}
 
int getpre(int l,int r,int x){
	return getkth(l,r,getrank(1,1,n,l,r,x));
}
 
int getnext(int l,int r,int x){
	return getkth(l,r,getrank(1,1,n,l,r,x+1)+1);
}
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	n=read(); m=read(); 
	srand(time(NULL));
	for(int i=1;i<=n;i++){
		a[i]=read();
		build(1,1,n,i,a[i]);
	}
	int opt,l,r,pos,x;
	while(m--){
		scanf("%d",&opt);
		switch(opt){
			case 1: l=read();r=read();x=read(); printf("%d\n",getrank(1,1,n,l,r,x)+1); break;
			case 2: l=read();r=read();x=read(); printf("%d\n",getkth(l,r,x)); break;
			case 3: pos=read();x=read(); if(a[pos]==x)break; update(1,1,n,pos,x); a[pos]=x; break;
			case 4: l=read();r=read();x=read(); printf("%d\n",getpre(l,r,x)); break;
			case 5: l=read();r=read();x=read(); printf("%d\n",getnext(l,r,x)); break;
		}
	}
	return 0;
}