记录编号	464986	评测结果	AAAAAAAAAAAA
题目名称	璐璐的治疗	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	2.706 s
提交时间	2017-10-26 17:12:04	内存使用	0.31 MiB

# include "iostream"
# include "stdio.h"
# include "algorithm"
# include "string.h"
# include "math.h"
# include "time.h"
# define size(x) ((x)?(x)->sz:(0))
# define ls(x) ((x)->ch[0])
# define rs(x) ((x)->ch[1])
using namespace std;
struct treap{
	   treap *ch[2];
	   int sz,val,rd;
	   treap(int x){ch[0]=ch[1]=NULL;sz=1;val=x;rd=rand();}
}*rt;
void turn(treap *&rt,int d){
	 treap *k=rt->ch[d^1];
	 rt->ch[d^1]=k->ch[d];
	 rt->sz=size(ls(rt))+size(rs(rt))+1;
	 k->ch[d]=rt;
     k->sz=size(ls(k))+size(rs(k))+1;
     rt=k;
}
void insert(treap *&rt,int x){
	 if(rt==NULL){
	 	rt=new treap(x);
	 	return;
	 }int d=x<(rt->val);
	 insert(rt->ch[d^1],x);
	 rt->sz=size(ls(rt))+size(rs(rt))+1;
	 if(rt->ch[d^1]->rd < rt->rd) turn(rt,d);
}/*
void insert(treap *&rt,int x){
	 if(!rt){
	 	rt=new treap(x);
	 	return;
	 }
	 int d=x < rt->val;
	 insert(rt->ch[d^1],x);
	 rt->sz=size(ls(rt))+size(rs(rt))+1;
	 if(rt->ch[d^1]->rd < rt->rd) turn(rt,d);
}*/
void del(treap *&rt,int x){
	 if(rt->val==x){
	 	if(ls(rt)&&rs(rt)){
	 	   int d=ls(rt)->rd < rs(rt)->rd;
	 	   turn(rt,d);
	 	   del(rt->ch[d],x);
	 	}
	 	else{
	 		treap *k=NULL;
	 		if(ls(rt)) k=ls(rt);
	 		else k=rs(rt);
	 		delete rt;
	 		rt=k;
	 	}
	 }
	 else{
	 	 int d=x < rt->val;
	 	 del(rt->ch[d^1],x);
	 }if(rt) rt->sz=size(ls(rt))+size(rs(rt))+1;
}
int kth(int rk){
    treap *k=rt;
    while(rk){
    	  if(size(ls(k))+1==rk) return k->val;
    	  if(size(ls(k))+1>rk) k=k->ch[0];
    	  else {rk-=size(ls(k))+1;k=rs(k);}
    }return 0;
}
int T,n,q,opt,ai,bi,ci;
int main(){
	freopen("ll.in","r",stdin);
	freopen("ll.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		  rt=NULL;
		  scanf("%d%d",&n,&q);
	      for(int i=1;i<=n;i++){
	      	  scanf("%d",&ai);
	      	  insert(rt,ai);
	      }
	      while(q--){
	      	    scanf("%d",&opt);
	      	    if(opt==1){scanf("%d",&bi);del(rt,bi);}
	      	    if(opt==2){scanf("%d",&bi);insert(rt,bi);}
	      	    if(opt==3){
	      	       scanf("%d%d",&ai,&bi);
 				   del(rt,ai);insert(rt,bi);
	      	    }
	      	    if(opt==4){
	      	       scanf("%d",&ai);
	      	       printf("%d\n",kth(ai));
	      	    }
	      }
	}

}
/*
1
5 7
10 20 50 30 40
4 3
1 20
2 25
3 50 35
4 4
3 10 30
4 3


30
35
30
*/