记录编号	399322	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	WildRage	是否通过	通过
代码语言	C++	运行时间	3.650 s
提交时间	2017-04-26 11:03:04	内存使用	1.27 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,m,rt<<1
#define rch m+1,r,rt<<1|1
using namespace std;
const int N=50005;
int n;
#define Treap 1
#ifdef Treap
struct Node{
	int v,key,size;
	Node *ch[2];
	Node(int x){
		v=x;key=rand();size=1;
		ch[0]=ch[1]=NULL;
	}
	#define size(_) ((_)?(_)->size:0)
	void Pushup(){
		size=size(ch[0])+size(ch[1])+1;
	}
};
void Turn_left(Node *&rt){
	Node *o=rt->ch[1];
	rt->ch[1]=o->ch[0];rt->Pushup();
	o->ch[0]=rt;o->Pushup();
	rt=o;
}
void Turn_right(Node *&rt){
	Node *o=rt->ch[0];
	rt->ch[0]=o->ch[1];rt->Pushup();
	o->ch[1]=rt;o->Pushup();
	rt=o;
}
void Insert(Node *&rt,int x){
	if(!rt){
		rt=new Node(x);
		return;
	}
	else if(x<rt->v){
		Insert(rt->ch[0],x);
		rt->Pushup();
		if(rt->ch[0]->key > rt->key) Turn_right(rt);
	}
	else {
		Insert(rt->ch[1],x);
		rt->Pushup();
		if(rt->ch[1]->key > rt->key) Turn_left(rt);
	}
}
void remove(Node *&rt,int x){
	if(rt->v==x){
		if(rt->ch[0]&&rt->ch[1]){
			if(rt->ch[0]->key > rt->ch[1]->key){
				Turn_right(rt);
				remove(rt->ch[1],x);
			}
			else{
				Turn_left(rt);
				remove(rt->ch[0],x);
			}
		}
		else{
			Node *o=NULL;
			if(rt->ch[0])o=rt->ch[0];
			else o=rt->ch[1];
			delete rt;
			rt=o;
		}
	}
	else{
		if(x<rt->v)remove(rt->ch[0],x);
		else remove(rt->ch[1],x);
	}
	if(rt)rt->Pushup();
}
int rank(Node *rt,int x){
	int ans=0;
	while(rt){
		if(x>rt->v)ans+=size(rt->ch[0])+1,rt=rt->ch[1];
		else rt=rt->ch[0];
	}
	return ans;
}
Node *kth(Node *rt,int k){
	while(rt){
		int _size=size(rt->ch[0])+1;
		if(_size==k)return rt;
		if(_size>=k)rt=rt->ch[0];
		else k-=_size,rt=rt->ch[1];
	}
}
#endif
Node *Man[N<<2];
int a[N];
void build(int l,int r,int rt){
	for(int i=l;i<=r;i++)Insert(Man[rt],a[i]);
}
void buildtree(int l,int r,int rt){
	build(l,r,rt);
	if(l==r)return;
	int m=(l+r)>>1;
	buildtree(lch);
	buildtree(rch);
}
int rank(int L,int R,int x,int l,int r,int rt){
	if(L<=l&&R>=r)
		return rank(Man[rt],x);
	int m=(l+r)>>1;
	if(R<=m)return rank(L,R,x,lch);
	if(L>m)return rank(L,R,x,rch);
	return rank(L,R,x,lch)+rank(L,R,x,rch);
}
int kth(int L,int R,int k){
	int l=1,r=1e8;
	while(l<=r){
		int m=(l+r)>>1;
		int num=rank(L,R,m,1,n,1)+1;
		if(num<=k)l=m+1;
		else r=m-1;
	}
	return r;
}
void Insert(int k,int x,int y,int l,int r,int rt){
	remove(Man[rt],y);
	Insert(Man[rt],x);
	if(l==r)return;
	int m=(l+r)>>1;
	if(k<=m)Insert(k,x,y,lch);
	else Insert(k,x,y,rch);
}
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	//for(int i=1;i<(N<<2);i++)Man[i]=NULL;
	buildtree(1,n,1);
	int op,l,r,k,pos;
	for(int i=1;i<=m;i++){
		scanf("%d",&op);
		switch(op){
			case 1:
				scanf("%d%d%d",&l,&r,&k);
				printf("%d\n",rank(l,r,k,1,n,1)+1);
				break;
			case 2:
				scanf("%d%d%d",&l,&r,&k);
				printf("%d\n",kth(l,r,k));
				break;
			case 3:
				scanf("%d%d",&pos,&k);
				Insert(pos,k,a[pos],1,n,1);
				a[pos]=k;
				break;
			case 4:
				scanf("%d%d%d",&l,&r,&k);
				printf("%d\n",kth(l,r,rank(l,r,k,1,n,1)));
				break;
			case 5:
				scanf("%d%d%d",&l,&r,&k);
				printf("%d\n",kth(l,r,rank(l,r,k+1,1,n,1)+1));
		}
	}
	//while(1);
}