记录编号	60617	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	切割矩形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.891 s
提交时间	2013-05-27 21:51:29	内存使用	2.47 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEL=30000*2+10;
const int SIZEN=30001;
int n,q,len;
class SEGMENT{
public:
	int l,r;
	int lchild,rchild;
	int sum;//区间和
};
SEGMENT ls[SIZEL],rs[SIZEL];//布雷区间的左,右端点数区间和
#define now s[root]
int tot;
void build(SEGMENT s[SIZEL],int root,int x,int y){
	now.l=x,now.r=y;
	now.sum=0;
	if(y>x){
		int mid=(x+y)>>1;
		now.lchild=++tot;
		build(s,tot,x,mid);
		now.rchild=++tot;
		build(s,tot,mid+1,y);
	}
	else{
		now.lchild=-1;
		now.rchild=-1;
	}
}
int getsum(SEGMENT s[SIZEL],int root,int x,int y){
	if(root==-1||now.r<x||now.l>y) return 0;
	if(now.l>=x&&now.r<=y) return now.sum;
	return getsum(s,now.lchild,x,y)+getsum(s,now.rchild,x,y);
}
void add(SEGMENT s[SIZEL],int root,int x,int k){//a[x]++
	if(root==-1||now.r<x||now.l>x) return;
	now.sum+=k;
	add(s,now.lchild,x,k);
	add(s,now.rchild,x,k);
}
class REQ{//request
public:
	int op;//操作种类
	//1是矩形进入,2是线段查询,3是矩形离开
	int ts;//时间戳
	int x1,x2;
};
bool operator < (REQ a,REQ b){
	if(a.ts!=b.ts) return a.ts<b.ts;
	return a.op<b.op;
}
vector<REQ> request;
vector<int> ab;//横坐标
map<int,int> lis;//first是绝对坐标,second是相对坐标
void init(void){
	request.clear();
	ab.clear();
	lis.clear();
	scanf("%d",&n);
	int i;
	int x1,x2,y1,y2;
	for(i=1;i<=n;i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		request.push_back((REQ){1,y1,x1,x2});
		request.push_back((REQ){3,y2,x1,x2});
		ab.push_back(x1),ab.push_back(x2);
	}
	scanf("%d",&q);
	n+=q;
	for(i=1;i<=q;i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		request.push_back((REQ){2,y1,x1,x2});
		ab.push_back(x1),ab.push_back(x2);
	}
	sort(request.begin(),request.end());
	sort(ab.begin(),ab.end());
	int temp=1;
	for(i=0;i<ab.size();i++){
		if(i==0||ab[i]!=ab[i-1]) lis[ab[i]]=temp++;
	}
	len=lis.size();
	tot=0;
	build(ls,0,1,len);
	tot=0;
	build(rs,0,1,len);
}
int ans;
void work(void){
	int count=0;
	ans=0;
	int i;
	int op,lnow,rnow,temp;
	for(i=0;i<request.size();i++){
		op=request[i].op;
		lnow=lis[request[i].x1],rnow=lis[request[i].x2];
		if(op==1){//矩形进入
			add(ls,0,lnow,1);
			add(rs,0,rnow,1);
			count++;
		}
		else if(op==3){//矩形离开
			add(ls,0,lnow,-1);
			add(rs,0,rnow,-1);
			count--;
		}
		else if(op==2){//查询
			temp=getsum(rs,0,1,lnow-1)+getsum(ls,0,rnow+1,len);
			ans+=(count-temp);
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("cutting.in","r",stdin);
	freopen("cutting.out","w",stdout);
	int T;
	scanf("%d",&T);
	int i;
	for(i=1;i<=T;i++){
		init();
		work();
	}
	return 0;
}