记录编号	456872	评测结果	AAAAAAAAAAAA
题目名称	2630. 璐璐的治疗	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	2.338 s
提交时间	2017-10-05 20:10:45	内存使用	0.77 MiB

# include "iostream"
# include "algorithm"
# include "stdio.h"
# include "string.h"
# include "math.h"
# include "time.h"
# define maxn 10005
using namespace std;
int t,n,m,zz,ai,bi,root,opt;
struct treap{int tot,sz,no,rd,ls,rs;}e[maxn*2];
void lx(int &rt){
	 int t=e[rt].rs;
	 e[rt].rs=e[t].ls;
	 e[t].ls=rt;
	 e[t].sz=e[rt].sz;
	 e[rt].sz=e[e[rt].ls].sz+e[e[rt].rs].sz+e[rt].tot;
	 rt=t;
}
void rx(int &rt){
	 int t=e[rt].ls;
	 e[rt].ls=e[t].rs;
	 e[t].rs=rt;
	 e[t].sz=e[rt].sz;
	 e[rt].sz=e[e[rt].ls].sz+e[e[rt].rs].sz+e[rt].tot;
	 rt=t;
} 
void insert(int &rt,int x){
	 if(!rt){
	 	rt=++zz;
	 	e[rt].no=x;
	 	e[rt].sz=e[rt].tot=1;
	 	e[rt].rd=rand();
	 	return;
	 }e[rt].sz++;
	 if(e[rt].no==x) e[rt].tot++;
	 else{
	 	 if(e[rt].no>x){
	 	 	 insert(e[rt].ls,x);
	 	 	 if(e[e[rt].ls].rd<e[rt].rd)
		        rx(rt);
		 }
		 else{
		 	 insert(e[rt].rs,x);
		 	 if(e[e[rt].rs].rd<e[rt].rd)
		 	    lx(rt);
		 }
	 }
}
void del(int &rt,int x){
	 if(!rt) return;
	 if(e[rt].no==x){
	 	if(e[rt].tot>1){
	 		e[rt].sz--;
	 		e[rt].tot--;
	 		return;
    	}
    	if(e[rt].ls*e[rt].rs==0)
    	   rt=e[rt].ls+e[rt].rs;
    	else{
    		if(e[e[rt].ls].rd<e[e[rt].rs].rd) rx(rt);
    		else lx(rt);
    		del(rt,x);
		}
	 }
	 else{
	 	e[rt].sz--;
	 	if(x>e[rt].no) del(e[rt].rs,x);
	 	else del(e[rt].ls,x);
	 }
}
int num(int &rt,int rk){
	if(!rt) return 0;
	if(e[e[rt].ls].sz+1<=rk&&e[e[rt].ls].sz+e[rt].tot>=rk)
	   return e[rt].no;
	if(e[e[rt].ls].sz>=rk) return num(e[rt].ls,rk);
	if(e[e[rt].ls].sz<rk) return num(e[rt].rs,rk-e[rt].tot-e[e[rt].ls].sz); 
}
int main(){
	freopen("ll.in","r",stdin);
	freopen("ll.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		  root=0;zz=0;
		  memset(e,0,sizeof e);
		  scanf("%d%d",&n,&m);
		  for(int i=1;i<=n;i++) {scanf("%d",&ai);insert(root,ai);}
	      while(m--){
	      	    scanf("%d",&opt);
				  switch(opt){
				  	 case(1):scanf("%d",&ai);del(root,ai);break;
				  	 case(2):scanf("%d",&ai);insert(root,ai);break;
				  	 case(3):scanf("%d%d",&ai,&bi);del(root,ai);insert(root,bi);break;
				  	 case(4):scanf("%d",&ai);printf("%d\n",num(root,ai));
				  } 
		  }
	}
}