记录编号	457038	评测结果	AAAAAAAAAAAA
题目名称	2630. 璐璐的治疗	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.990 s
提交时间	2017-10-06 15:44:23	内存使用	0.31 MiB

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
#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;
	}
}*root;
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 kth(int k){
	node *now(root);
	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 t,n,m;
inline void clear(node *&x){
	if(!x)return;
	if(x->lch)
		clear(x->lch);
	if(x->rch)
		clear(x->rch);
	delete x;
}
int main(){
	freopen("ll.in","r",stdin);
	freopen("ll.out","w",stdout);
	t=read();
	while(t--){
//		clear(root);
		n=read(),m=read();
		root=NULL;
		for(int i=1;i<=n;++i){
			int x(read());
			insert(root,x);
		}
		while(m--){
			int op(read());
			if(op==1){
				int x(read());
				del(root,x);
			}
			if(op==2){
				int x(read());
				insert(root,x);
			}
			if(op==3){
				int x(read()),y(read());
				del(root,x);
				insert(root,y);
			}
			if(op==4){
				int x(read());
				printf("%d\n",kth(x));
			}
		}
	}
}