记录编号	410783	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]Attack	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	21.142 s
提交时间	2017-06-02 16:16:53	内存使用	355.25 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10,M=3e7+10;
struct Node{int l,r,v;}node[M];
int n,m,id,x[N],y[N],z[N],ax[N],ay[N],az[N];
int rankl(int *a,int x){//第一个>=x的数
	int l=0,r=n+1;
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid]>=x) r=mid;else l=mid+1;
	}
	return l;
}
int rankr(int *a,int x){//第一个<=x的数
	int l=0,r=n+1;
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
void add(int x,int p,int d){//一维单点修改
	int l=1,r=n;
	while (1){
		node[x].v+=d;
		if (l==r) return;
		int mid=(l+r)>>1;
		if (p>mid){
			if (!node[x].r) node[x].r=++id;
			x=node[x].r;
			l=mid+1;
		}
		else{
			if (!node[x].l) node[x].l=++id;
			x=node[x].l;
			r=mid;
		}
	}
}
int sum(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return node[x].v;
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans+=sum(node[x].l,l,mid,L,R);
	if (R>mid) ans+=sum(node[x].r,mid+1,r,L,R);
	return ans;
}
void ins(int X,int Y,int d){
	int l=1,r=n,x=1;
	while (1){
		if (!node[x].v) node[x].v=++id;
		add(node[x].v,Y,d);
		if (l==r) return;
		int mid=(l+r)>>1;
		if (X>mid){
			if (!node[x].r) node[x].r=++id;
			x=node[x].r;
			l=mid+1;
		}
		else{
			if (!node[x].l) node[x].l=++id;
			x=node[x].l;
			r=mid;
		}
	}
}
int sum(int x,int l,int r,int x1,int y1,int x2,int y2){
	if (l>=x1&&r<=x2) return sum(node[x].v,1,n,y1,y2);
	int mid=(l+r)>>1,ans=0;
	if (x1<=mid) ans+=sum(node[x].l,l,mid,x1,y1,x2,y2);
	if (x2>mid) ans+=sum(node[x].r,mid+1,r,x1,y1,x2,y2);
	return ans;
}
struct opt{int id,tp,x1,y1,x2,y2,k,d;}Q[N];
int ans[N],cnt;bool ask[N];
//d=+-1表示修改，否则表示查询
bool cmp(const opt &x,const opt &y){return x.tp==y.tp?x.id<y.id:x.tp<y.tp;}
void solve(int l,int r,int L,int R){//答案区间为[l,r]，操作区间为[L,R]
	if (L>R) return;
	if (l==r){
		for (int i=L;i<=R;i++)
			if (!Q[i].d) ans[Q[i].id]=l;
		return;
	}
	int cnt=0;
	//初始化
	for (;id;id--) node[id].l=node[id].r=node[id].v=0;id=1;
	int mid=(l+r)>>1;
	for (int i=L;i<=R;i++)
	if (Q[i].d){
		if (Q[i].k<=mid) ins(Q[i].x1,Q[i].y1,Q[i].d),Q[i].tp=0,cnt++;
			else Q[i].tp=1;
	}
	else{
		int s;
		if (Q[i].x1>Q[i].x2||Q[i].y1>Q[i].y2) s=0;
			else s=sum(1,1,n,Q[i].x1,Q[i].y1,Q[i].x2,Q[i].y2);
		if (s>=Q[i].k) Q[i].tp=0,cnt++;
			else Q[i].k-=s,Q[i].tp=1;
	}
	sort(Q+L,Q+R+1,cmp);
	solve(l,mid,L,L+cnt-1);
	solve(mid+1,r,L+cnt,R);
}
int main()
{
	freopen("nt2012_attack.in","r",stdin);
	freopen("nt2012_attack.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
		ax[i]=x[i];ay[i]=y[i];az[i]=z[i];
	}
	sort(ax+1,ax+n+1);ax[n+1]=1e9;
	sort(ay+1,ay+n+1);ay[n+1]=1e9;
	sort(az+1,az+n+1);az[n+1]=1e9;
	for (int i=1;i<=n;i++){
		x[i]=rankl(ax,x[i]);
		y[i]=rankl(ay,y[i]);
		z[i]=rankl(az,z[i]);
		cnt++;Q[cnt]=(opt){cnt,0,x[i],y[i],0,0,z[i],1};
	}
	char tp[10];int x1,y1,x2,y2,k;
	while (m--){
		scanf("%s%d%d",tp,&x1,&y1);
		if (tp[0]=='Q'){
			scanf("%d%d%d",&x2,&y2,&k);
			if (x1>x2) swap(x1,x2);
			if (y1>y2) swap(y1,y2);
			x1=rankl(ax,x1);
			y1=rankl(ay,y1);
			x2=rankr(ax,x2);
			y2=rankr(ay,y2);
			//printf("[(%d,%d),(%d,%d)]\n",x1,y1,x2,y2);
			ask[++cnt]=1;
			Q[cnt]=(opt){cnt,0,x1,y1,x2,y2,k,0};
		}
		else{
			x1++;y1++;
			cnt++;Q[cnt]=(opt){cnt,0,x[x1],y[x1],0,0,z[x1],-1};
			cnt++;Q[cnt]=(opt){cnt,0,x[y1],y[y1],0,0,z[y1],-1};
			swap(z[x1],z[y1]);
			cnt++;Q[cnt]=(opt){cnt,0,x[x1],y[x1],0,0,z[x1],1};
			cnt++;Q[cnt]=(opt){cnt,0,x[y1],y[y1],0,0,z[y1],1};
		}
	}
	solve(1,n+1,1,cnt);
	for (int i=1;i<=cnt;i++) if (ask[i])
		ans[i]<=n?printf("%d\n",az[ans[i]]):puts("It doesn't exist.");
	return 0;
}