记录编号	431434	评测结果	AAAAAAAAAAAA
题目名称	璐璐的治疗	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	2.703 s
提交时间	2017-07-31 19:16:59	内存使用	16.32 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
/*
	以血量为坐标，建立坐标系；
	权值表示该血量人数； 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxd=(1<<20)+500;
int t,n,m;
int sum[maxd*4];
inline void add(int o,int l,int r,int nl,int nr,int v){
	if(l>=nl&&r<=nr){
		sum[o]+=v;
		return ;
	}
	int m=(l+r)>>1;
	int ls=o<<1;
	int rs=ls+1;
	if(m>=nl){add(ls,l,m,nl,nr,v);}
	if(m<nr){add(rs,m+1,r,nl,nr,v);}
	sum[o]=sum[ls]+sum[rs];
}
inline int kth(int o,int l,int r,int k){
	if(l==r)return l;
	int m=(l+r)>>1;
	int ls=o<<1;
	int rs=ls+1;
	if(sum[ls]>=k){return kth(ls,l,m,k);}
	else return kth(rs,m+1,r,k-sum[ls]); 
}
int main(){
	freopen("ll.in","r",stdin);
	freopen("ll.out","w",stdout);
	t=read();
	while(t--){
		n=read();m=read();
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;i++){
			int c=read();
			add(1,1,maxd,c,c,1);
		}
		for(int i=1;i<=m;i++){
			int c,x,y;
			c=read();
			if(c==1){
				x=read();
				add(1,1,maxd,x,x,-1);
			}
			if(c==2){
				x=read();
				add(1,1,maxd,x,x,1);
			}
			if(c==3){
				x=read();y=read();
				add(1,1,maxd,x,x,-1);
				add(1,1,maxd,y,y,1);
			}
			if(c==4){
				x=read();
				printf("%d\n",kth(1,1,maxd,x));
			}
		}
	}
	return 0;
}