记录编号	457249	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.681 s
提交时间	2017-10-07 11:18:01	内存使用	18.11 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 205000
using namespace std;
int num,ans[N],n,m;
struct data{
	int x,y,val,pos,opt,id;//opt 0:修改 1:查询  
}d[N],tmp[N];
bool cmp(data a,data b){
	if(a.x==b.x&&a.y==b.y)return a.opt<b.opt;
	return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
void pre_work(){
	int x1,x2,y1,y2;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);++num;
	d[++m].pos=num;d[m].x=x1-1;d[m].y=y1-1;d[m].val=1;d[m].opt=1;
	d[++m].pos=num;d[m].x=x2;d[m].y=y2;d[m].val=1;d[m].opt=1; 
	d[++m].pos=num;d[m].x=x2;d[m].y=y1-1;d[m].val=-1;d[m].opt=1; 
	d[++m].pos=num;d[m].x=x1-1;d[m].y=y2;d[m].val=-1;d[m].opt=1; 
	return;
}

int c[2000050];
void add(int x,int y){
	for(;x<=n;x+=(x&-x))c[x]+=y;
}
int query(int x){
	int cnt=0;
	for(;x;x-=(x&-x))cnt+=c[x];
	return cnt;
}

void CDQ(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1,l1=l,l2=mid+1;
	for(int i=l;i<=r;i++){
		if(d[i].id<=mid&&d[i].opt==0){
			add(d[i].y,d[i].val);
			//printf("%d  %d  %d\n",d[i].y,d[i].val,query(d[i].y));
		}
		if(d[i].id>mid&&d[i].opt==1){
			ans[d[i].pos]+=d[i].val*query(d[i].y);
			//printf("%d  %d\n",d[i].pos,ans[d[i].pos]);
		}
	}
	for(int i=l;i<=r;i++)if(d[i].id<=mid&&d[i].opt==0)add(d[i].y,-d[i].val);
	for(int i=l;i<=r;i++){
		if(d[i].id<=mid)tmp[l1++]=d[i];
		else tmp[l2++]=d[i];
	}
	for(int i=l;i<=r;i++)d[i]=tmp[i];
	CDQ(l,mid); CDQ(mid+1,r);
	return ; 
}
int main(){
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	int opt;
	scanf("%d%d",&opt,&n);
	while(1){
		scanf("%d",&opt);
		if(opt==1){m++;scanf("%d%d%d",&d[m].x,&d[m].y,&d[m].val);}
		if(opt==2){pre_work();}
		if(opt==3)break;
	}
	for(int i=1;i<=m;i++)d[i].id=i;
	//for(int i=1;i<=m;i++)
		//printf("%d  %d  %d  %d  %d  %d  %d\n",i,d[i].id,d[i].x,d[i].y,d[i].opt,d[i].val,d[i].pos);
	sort(d+1,d+m+1,cmp);
	//for(int i=1;i<=m;i++)
		//printf("%d  %d  %d  %d  %d  %d  %d\n",i,d[i].id,d[i].x,d[i].y,d[i].opt,d[i].val,d[i].pos);
	CDQ(1,m);
	for(int i=1;i<=num;i++)
		printf("%d\n",ans[i]);
	return 0;
}
/*
0 4 
1 2 3 3 
2 1 1 3 3 
1 2 2 2 
2 2 2 3 4 
3
*/