记录编号	151698	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]Attack	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	21.055 s
提交时间	2015-03-09 18:59:08	内存使用	256.77 MiB

//attack
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

#define l(x) ch[x][0]
#define r(x) ch[x][1]

const int Maxn=60010,Maxm=10010,Maxb=1050;
const int INF=0x3f3f3f3f;

using namespace std;

struct node{
	int x,y,v,pos;
}P[Maxn];

struct Asks{
	int type,x0,y0,x1,y1,k,v;
}A[Maxm];

int m,n,tot=0,ch[20000010][2],sumt[20000010];
int rank[Maxn],X[Maxn],bein[Maxn];
vector<int> lim,nodes[2];

int build(int l,int r){
	int x=++tot; sumt[x]=0;
	if(l==r) return x;
	int mid=(l+r)>>1;
	l(x)=build(l,mid);
	r(x)=build(mid+1,r);
	return x;
}

bool cmp_(node a,node b){
	return a.y<b.y;
}

int insert(int o,int l,int r,int qx){
	int x=++tot;
	l(x)=l(o); r(x)=r(o); sumt[x]=sumt[o]+1;
	if(l==r) return x;
	int mid=(l+r)>>1;
	if(qx<=mid) l(x)=insert(l(o),l,mid,qx);
	else r(x)=insert(r(o),mid+1,r,qx);
	return x;
}

int av[Maxn],Nv,tot_v=0,tot_x=0;

struct Block{
	node P[Maxb];
	int Y[Maxb],siz,mem_begin,root[Maxb],num;
	void add_node(node a){
		P[++siz]=a;
	}
	void make_tree(){
		tot=mem_begin;
		root[0]=1;
		for(int i=1;i<=siz;i++)
			root[i]=insert(root[i-1],1,Nv,P[i].v);
	}
	int calc(int x0,int y0,int x1,int y1,int L,int R){
		int ans=0;
		for(int i=1;i<=siz;i++)
			if(P[i].x<=x1&&P[i].x>=x0&&P[i].y<=y1&&P[i].y>=y0)
			    ans+=(P[i].v<=R&&P[i].v>=L? 1:0);
		return ans;
	}
	void init(){
		sort(P+1,P+siz+1,cmp_);
		make_tree();
		Y[0]=-INF; Y[siz+1]=INF;
		for(int i=1;i<=siz;i++)
		    bein[P[i].pos]=num,rank[P[i].pos]=i,Y[i]=P[i].y;
	}
}B[Maxb]={0};

int belong[Maxn],cntB;

bool cmpx(node a,node b){
	return a.x<b.x;
}

void move(int x){
	for(int i=0;i<nodes[0].size();i++)
		nodes[0][i]=ch[nodes[0][i]][x],nodes[1][i]=ch[nodes[1][i]][x];
}

int _queryL(int x0,int y0,int x1,int y1,int L,int R){
	int ans=0,mid=(L+R)>>1;
	for(int i=0;i<lim.size();i++) ans+=B[lim[i]].calc(x0,y0,x1,y1,L,mid);
	for(int i=0;i<nodes[0].size();i++){
		ans+=sumt[l(nodes[1][i])];
		ans-=sumt[l(nodes[0][i])];
	}
	return ans;
}

int _query(int x0,int y0,int x1,int y1,int L,int R){
	int ans=0;
	for(int i=0;i<lim.size();i++) ans+=B[lim[i]].calc(x0,y0,x1,y1,L,R);
	for(int i=0;i<nodes[0].size();i++){
		ans+=sumt[nodes[1][i]];
		ans-=sumt[nodes[0][i]];
	}
	return ans;
}

void Push_in(int l,int r,int yL,int yR){
	int lb=belong[l],rb=belong[r];
	lim.clear(); nodes[0].clear(); nodes[1].clear();
	lim.push_back(lb);
	if(lb!=rb) lim.push_back(rb);
	int lt,rt;
	for(int i=lb+1;i<rb;i++){
		lt=lower_bound(B[i].Y,B[i].Y+B[i].siz+2,yL)-B[i].Y;
		rt=upper_bound(B[i].Y,B[i].Y+B[i].siz+2,yR)-B[i].Y-1;
		rt=min(rt,B[i].siz),lt=max(lt,1);
		if(!rt) continue;
		nodes[0].push_back(B[i].root[lt-1]);
		nodes[1].push_back(B[i].root[rt]);
	}
}

void query(int x0,int y0,int x1,int y1,int k){
	if(x0>x1) swap(x0,x1);
	if(y0>y1) swap(y0,y1);
	int Lx=lower_bound(X,X+n+2,x0)-X;
	int Rx=upper_bound(X,X+n+2,x1)-X-1;
	if(!Rx){
		puts("It doesn't exist.");
		return;
	}
	Rx=min(Rx,n),Lx=max(Lx,1);
	Push_in(Lx,Rx,y0,y1);
	int l=1,r=Nv;
	if(_query(x0,y0,x1,y1,l,r)<k){
		puts("It doesn't exist.");
		return;
	}
	while(l<r){
		int tmp=_queryL(x0,y0,x1,y1,l,r),mid=(l+r)>>1;
		if(tmp<k) k-=tmp,l=mid+1,move(1);
		else r=mid,move(0);
	}
	printf("%d\n",av[l]);
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].v);
		P[i].pos=i;
		av[++tot_v]=P[i].v;
	}
	sort(P+1,P+n+1,cmpx);
	for(int i=1;i<=n;i++) X[i]=P[i].x;
	char str[11];
	for(int i=1;i<=m;i++){ 
		scanf("%s%d%d",str,&A[i].x0,&A[i].y0);
		A[i].type= str[0]=='Q';
		if(A[i].type) scanf("%d%d%d",&A[i].x1,&A[i].y1,&A[i].k);
		else A[i].x0++,A[i].y0++;
	}
	sort(av+1,av+tot_v+1);
	Nv=1;
	for(int i=2;i<=tot_v;i++)
	    if(av[i]!=av[i-1]) av[++Nv]=av[i];
	for(int i=1;i<=n;i++)
		P[i].v=lower_bound(av+1,av+Nv+1,P[i].v)-av;
}

void make_block(){
	int blcsiz=(int)sqrt(n+0.5);
	build(1,Nv);
	for(int i=1;i<=n;i++)
		belong[i]=(i-1)/blcsiz+1;
	cntB=(n-1)/blcsiz+1;
	for(int i=1;i<=n;i++) B[belong[i]].add_node(P[i]);
	B[1].mem_begin=tot+2;
	B[1].num=1;
	for(int i=2;i<=cntB;i++)
		B[i].mem_begin=B[i-1].mem_begin+Maxb*25,B[i].num=B[i-1].num+1;
	for(int i=1;i<=cntB;i++) B[i].init();
}

void solve(){
	X[0]=-INF; X[n+1]=INF;
	for(int i=1;i<=m;i++){
		if(A[i].type)
			query(A[i].x0,A[i].y0,A[i].x1,A[i].y1,A[i].k);
		else if(A[i].x0!=A[i].y0){
			int x=rank[A[i].x0],xb=bein[A[i].x0];
			int y=rank[A[i].y0],yb=bein[A[i].y0];
			swap(B[xb].P[x].v,B[yb].P[y].v);
			B[xb].make_tree();
			if(xb!=yb) B[yb].make_tree();
		}
	}
}

int main(){
	freopen("nt2012_attack.in","r",stdin);
	freopen("nt2012_attack.out","w",stdout);
	init();
	make_block();
	solve();
	return 0;
}