记录编号	464320	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.307 s
提交时间	2017-10-25 16:46:47	内存使用	20.15 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int n,m,que,tr[2000005],ans[800005];
struct node{int x,y,val,que,id,opt;inline bool operator<(const node &b)const{if(x==b.x&&y==b.y)return opt<b.opt;return x==b.x?y<b.y:x<b.x;}}q[200005],tmp[200005];
inline void update(int pos,int x){for(;pos<=n;pos+=pos&-pos)tr[pos]+=x;}
inline int sum(int pos){int ret(0);for(;pos;pos-=pos&-pos)ret+=tr[pos];return ret;}
inline void add_query(){
	int a(read()),b(read()),c(read()),d(read());++que;
	q[++m].que=que;q[m].x=a-1;q[m].y=b-1;q[m].val=1;q[m].opt=1;
	q[++m].que=que;q[m].x=c;q[m].y=d;q[m].val=1;q[m].opt=1;
	q[++m].que=que;q[m].x=a-1;q[m].y=d;q[m].val=-1;q[m].opt=1;
	q[++m].que=que;q[m].x=c;q[m].y=b-1;q[m].val=-1;q[m].opt=1;
}
inline void CDQ(int l,int r){
	if(l==r)return;
	int mid((l+r)>>1),tp1(l),tp2(mid+1);
	for(int i=l;i<=r;++i){
		if(q[i].id<=mid&&!q[i].opt)update(q[i].y,q[i].val);
		if(q[i].id>mid&&q[i].opt)ans[q[i].que]+=q[i].val*sum(q[i].y);
	}
	for(int i=l;i<=r;++i)if(q[i].id<=mid&&!q[i].opt)update(q[i].y,-q[i].val);
	for(int i=l;i<=r;++i)if(q[i].id<=mid)tmp[tp1++]=q[i];else tmp[tp2++]=q[i];
	for(int i=l;i<=r;++i)q[i]=tmp[i];
	CDQ(l,mid);CDQ(mid+1,r);
}
int main(){
	freopen("mokia.in","r",stdin);freopen("mokia.out","w",stdout);
	n=read(),n=read();
	while(1){
		int op(read());
		if(op==1)++m,q[m].x=read(),q[m].y=read(),q[m].val=read();
		else if(op==2)add_query();
		else break;
	}
	for(int i=1;i<=m;++i)q[i].id=i;
	sort(q+1,q+m+1);CDQ(1,m);
	for(int i=1;i<=que;++i)printf("%d\n",ans[i]);
}