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

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int size,key,fix;
	node(int x=0):lch(NULL),rch(NULL),size(1),key(x),fix(rand()){}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
	}
}*tr[200005];
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v){
	if(!x){
		x=new node(v);
		return;
	}
	if(v<=x->key){
		insert(x->lch,v);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline void del(node *&x,int v){
	if(x->key==v){
		if(x->lch&&x->rch){
			if(x->lch->fix<x->rch->fix){
				right_rotate(x);
				del(x->rch,v);
			}
			else{
				left_rotate(x);
				del(x->lch,v);
			}
		}
		else{
			node *tmp(NULL);
			if(x->lch)
				tmp=x->lch;
			else
				tmp=x->rch;
			delete x;
			x=tmp;
		}
	}
	else{
		if(v<=x->key)
			del(x->lch,v);
		else
			del(x->rch,v);
	}
	if(x)
		x->pushup();
}
inline int Rank(node *now,int x){
	int ret(0);
	while(now){
		if(x<=now->key)
			now=now->lch;
		else
			ret+=get_size(now->lch)+1,now=now->rch;
	}
	return ret;
}
inline int kth(node *now,int k){
	while(now){
		if(get_size(now->lch)+1==k)
			return now->key;
		if(get_size(now->lch)+1>=k)
			now=now->lch;
		else
			k-=get_size(now->lch)+1,now=now->rch;
	}
}
int n,m;
int a[50005];
inline void build(int l,int r,int rt){
	for(int i=l;i<=r;++i)
		insert(tr[rt],a[i]);
	if(l==r)return;
	int mid((l+r)>>1);
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
inline int Rank(int ll,int rr,int k,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return Rank(tr[i],k);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)
		ret+=Rank(ll,rr,k,l,mid,i<<1);
	if(mid<rr)
		ret+=Rank(ll,rr,k,mid+1,r,i<<1|1);
	return ret;
}
inline int kth(int l,int r,int k){
	int ll(1),rr(1e8);
	while(ll<=rr){
		int mid((ll+rr)>>1);
		int jud(Rank(l,r,mid,1,n,1)+1);
		if(jud<=k)
			ll=mid+1;
		else
			rr=mid-1;
	}
	return rr;
}
inline void update(int pos,int w,int l,int r,int i){
	del(tr[i],a[pos]);
	insert(tr[i],w);
	if(l==r)return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(pos,w,l,mid,i<<1);
	else
		update(pos,w,mid+1,r,i<<1|1);
}
inline int gg(){
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	srand(time(NULL));
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	build(1,n,1);
	while(m--){
		int op(read());
		if(op==1){
			int x(read()),y(read()),z(read());
			printf("%d\n",Rank(x,y,z,1,n,1)+1);
		}
		if(op==2){
			int x(read()),y(read()),z(read());
			printf("%d\n",kth(x,y,z));
		}
		if(op==3){
			int x(read()),y(read());
			update(x,y,1,n,1);
			a[x]=y;
		}
		if(op==4){
			int x(read()),y(read()),z(read());
			printf("%d\n",kth(x,y,Rank(x,y,z,1,n,1)));
		}
		if(op==5){
			int x(read()),y(read()),z(read());
			printf("%d\n",kth(x,y,Rank(x,y,z+1,1,n,1)+1));
		}
	}
	return 0;
}
int K(gg());
int main(){;}