记录编号	133856	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]Attack	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	24.439 s
提交时间	2014-10-28 20:52:03	内存使用	112.66 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEB=310,SIZEN=60010,BLOCK_NODE=SIZEB*30;
class NODE{//函数式线段树的节点
public:
	int sum;
	int l,r;
	int lson,rson;
	void print(void){cout<<l<<" "<<r<<" "<<sum<<" "<<lson<<" "<<rson<<endl;}
	void clear(int a,int b){
		l=a,r=b;
		sum=0;
		lson=rson=-1;
	}
};
NODE tree[SIZEN*100];
int tot=0;
void printtree(int x){//调试接口......
	cout<<x<<":  ";tree[x].print();
	if(tree[x].lson!=-1) printtree(tree[x].lson);
	if(tree[x].rson!=-1) printtree(tree[x].rson);
}
int build(int l,int r){
	int x=tot++;
	tree[x].clear(l,r);
	if(l<r){
		int mid=(l+r)/2;
		tree[x].lson=build(l,mid);
		tree[x].rson=build(mid+1,r);
	}
	return x;
}
int change(int x,int a,int t){
	if(x==-1) return -1;
	if(tree[x].l>a||tree[x].r<a) return x;
	int p=tot++;
	tree[p]=tree[x];
	NODE &now=tree[p];
	now.sum+=t;
	now.lson=change(now.lson,a,t);
	now.rson=change(now.rson,a,t);
	return p;
}
int leftsum(int x){//左儿子的sum
	return tree[tree[x].lson].sum;
}
class CITY{//城池
public:
	int id;
	int x,y,z;
	void print(void){cout<<x<<" "<<y<<" "<<z<<endl;}
};
bool cmpx(CITY a,CITY b){
	return a.x<b.x;
}
bool cmpy(CITY a,CITY b){
	return a.y<b.y;
}
bool cmpz(CITY a,CITY b){
	return a.z<b.z;
}
int WN;//权值的个数,从1到wn编号
int N,Q;
int T,BN;//每一块大小,块数
int belong[SIZEN],bpos[SIZEN];
int realz[SIZEN];
CITY cities[SIZEN];
class BLOCK{//分块后的一块
public:
	int len;
	int stx,edx;//开始和结束的x
	CITY c[SIZEB];
	int Y[SIZEB];
	int root[SIZEB];
	int head;//从这里开始
	BLOCK(){len=0;}
	void add(CITY t){
		if(!len) stx=t.x;
		c[++len]=t;
		edx=t.x;
	}
	int stat(int x0,int y0,int x1,int y1,int l,int r){//在矩形内且z属于[k,r]的数量
		int ans=0;
		for(int i=1;i<=len;i++){
			if(c[i].x<x0||c[i].x>x1||c[i].y<y0||c[i].y>y1) continue;
			if(c[i].z<l||c[i].z>r) continue;
			ans++;
		}
		return ans;
	}
	pair<int,int> get_window(int y0,int y1){//看y符合的是哪一段
		pair<int,int> ans;
		ans.first=lower_bound(Y+1,Y+1+len,y0)-Y;
		ans.second=upper_bound(Y+1,Y+1+len,y1)-Y-1;
		return ans;
	}
	void maketree(void){
		tot=head;//放在分给它的内存中
		root[0]=0;//在每个block里它都是零......不要在意
		for(int i=1;i<=len;i++) root[i]=change(root[i-1],c[i].z,1);
	}
	void init(void){//按y排序,并建树
		sort(c+1,c+1+len,cmpy);
		maketree();
		for(int i=1;i<=len;i++){
			bpos[c[i].id]=i;
			Y[i]=c[i].y;
		}
	}
}blocks[SIZEB];
vector<int> part;//两端的块
int full_l,full_r;//完整的
int nd0[SIZEB],nd1[SIZEB];//负,正节点的坐标
void mark_blocks(int a,int b){//得出中间/两端的块都有哪些,查询的x范围a~b
	part.clear();
	full_l=full_r=0;
	for(int i=1;i<=BN;i++){
		if(blocks[i].stx>b||blocks[i].edx<a) continue;
		if(blocks[i].stx>=a&&blocks[i].edx<=b){
			if(!full_l) full_l=i;
			full_r=i;
		}
		else part.push_back(i);
	}
}
void get_node(int y0,int y1){//得到"正节点"和"负节点"(区间和,也就是两棵线段树做减法)
	pair<int,int> tp;
	for(int i=full_l;i<=full_r;i++){
		tp=blocks[i].get_window(y0,y1);
		nd0[i]=blocks[i].root[tp.first-1];
		nd1[i]=blocks[i].root[tp.second];
	}
}
int calc_num(int x0,int y0,int x1,int y1,int l,int r){//计算矩形框内,z在[l,r]的数量
	int ans=0;
	for(int i=0;i<part.size();i++) ans+=blocks[part[i]].stat(x0,y0,x1,y1,l,r);
	for(int i=full_l;i<=full_r;i++){
		ans-=tree[nd0[i]].sum;
		ans+=tree[nd1[i]].sum;
	}
	return ans;
}
int calc_left(int x0,int y0,int x1,int y1,int l,int r){//计算矩形框内,z在[l,r]的左边一半的数量
	int ans=0,mid=(l+r)/2;
	for(int i=0;i<part.size();i++) ans+=blocks[part[i]].stat(x0,y0,x1,y1,l,mid);
	for(int i=full_l;i<=full_r;i++){
		ans-=leftsum(nd0[i]);
		ans+=leftsum(nd1[i]);
	}
	return ans;
}
void go_down(bool flag){//每个节点都向左/右儿子走,0左1右
	for(int i=full_l;i<=full_r;i++){
		if(!flag){
			nd0[i]=tree[nd0[i]].lson;
			nd1[i]=tree[nd1[i]].lson;
		}
		else{
			nd0[i]=tree[nd0[i]].rson;
			nd1[i]=tree[nd1[i]].rson;
		}
	}
}
void answer(int x0,int y0,int x1,int y1,int k){
	mark_blocks(x0,x1);
	get_node(y0,y1);
	int l=1,r=WN;
	if(calc_num(x0,y0,x1,y1,l,r)<k){
		printf("It doesn't exist.\n");
		return;
	}
	while(l<r){//二分离散化后的值
		int t=calc_left(x0,y0,x1,y1,l,r);
		int mid=(l+r)/2;
		if(t<k){
			k-=t;
			l=mid+1;
			go_down(1);
		}
		else{
			r=mid;
			go_down(0);
		}
	}
	printf("%d\n",realz[l]);
}
void change(int a,int b){//交换二者
	if(a==b) return;
	swap(blocks[belong[a]].c[bpos[a]].z,blocks[belong[b]].c[bpos[b]].z);
	blocks[belong[a]].maketree();
	if(belong[b]!=belong[a]) blocks[belong[b]].maketree();
}
void work(void){
	char cmd[20];
	int x0,y0,x1,y1,k;
	int x,y;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		if(cmd[0]=='Q'){
			scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&k);
			if(x0>x1) swap(x0,x1);//反人类的输入格式......
			if(y0>y1) swap(y0,y1);
			answer(x0,y0,x1,y1,k);
		}
		else{
			scanf("%d%d",&x,&y);
			x++,y++;
			change(x,y);
		}
	}
}
void allot_head(void){//给每一个块设置它在线段树中的内存起点
	for(int i=1;i<=BN;i++){
		blocks[i].head=tot;
		tot+=BLOCK_NODE;
	}
}
void make_blocks(void){//分好块
	WN=0;
	sort(cities+1,cities+1+N,cmpz);
	int last;
	for(int i=1;i<=N;i++){//将z离散化
		if(i==1||cities[i].z!=last){
			WN++;
			realz[WN]=cities[i].z;
		}
		last=cities[i].z;
		cities[i].z=WN;
	}
	sort(cities+1,cities+1+N,cmpx);
	T=sqrt(N+0.5);
	BN=1;int tot=0;
	for(int i=1;i<=N;i++){//按x分块
		tot++;
		belong[cities[i].id]=BN;
		blocks[BN].add(cities[i]);
		if(i==N||tot==T){
			BN++;
			tot=0;
		}
	}
	BN--;
	build(1,WN);
	allot_head();
	for(int i=1;i<=BN;i++) blocks[i].init();//该块初始化
}
void read(void){
	scanf("%d%d",&N,&Q);
	for(int i=1;i<=N;i++){
		cities[i].id=i;
		scanf("%d%d%d",&cities[i].x,&cities[i].y,&cities[i].z);
	}
}
int main(){
	freopen("nt2012_attack.in","r",stdin);
	freopen("nt2012_attack.out","w",stdout);
	read();
	make_blocks();
	work();
	return 0;
}