记录编号	229821	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	4.605 s
提交时间	2016-02-20 19:46:45	内存使用	95.74 MiB

//YMX
#include<cstdio>
#include<algorithm>
int EPX,c,n,t,t1,t2,ans[510000];
inline void in(int &X)
{
	for(X=getchar();X<48||X>57;X=getchar());
	X^=48;
	for(EPX=getchar();47<EPX&&EPX<58;EPX=getchar())
		X=(X<<1)+(X<<3)+(EPX^48);
}
struct event
{
	int x,y,w,id,t;
	bool flag;
}o[2100000],tmp[2100000];
inline bool comp(event a,event b)
{
	if(a.x==b.x&&a.y==b.y)
		return a.flag<b.flag;
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline void add()
{
	int x1,y1,x2,y2;
	in(x1),in(y1),in(x2),in(y2),++ans[0];
	o[++t].id=ans[0];o[t].x=x1-1,o[t].y=y1-1,o[t].w= 1,o[t].flag=1,o[t].t=t;
	o[++t].id=ans[0];o[t].x=x1-1,o[t].y=  y2,o[t].w=-1,o[t].flag=1,o[t].t=t;
	o[++t].id=ans[0];o[t].x=  x2,o[t].y=y1-1,o[t].w=-1,o[t].flag=1,o[t].t=t;
	o[++t].id=ans[0];o[t].x=  x2,o[t].y=  y2,o[t].w= 1,o[t].flag=1,o[t].t=t;
}
int tree[2100000];
inline void ADD(int x,int w)
{
	while(x<=n)
	{
		tree[x]+=w;
		x+=x&(-x);
	}
}
inline int sum(int x)
{
	int end=0;
	while(x)
	{
		end+=tree[x];
		x-=x&(-x);
	}
	return end;
}
inline 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(o[i].t<=mid&&!o[i].flag)
			ADD(o[i].y,o[i].w);
		else if(o[i].t>mid&&o[i].flag)
			ans[o[i].id]+=o[i].w*sum(o[i].y);
	}
	for(int i=l;i<=r;++i)
		if(o[i].t<=mid&&!o[i].flag)
			ADD(o[i].y,-o[i].w);//这是撤销操作！
	for(int i=l;i<=r;++i)
		if(o[i].t<=mid)
			tmp[l1++]=o[i];
		else
			tmp[l2++]=o[i];
	for(int i=l;i<=r;++i)
		o[i]=tmp[i];
	CDQ(l,mid);
	CDQ(mid+1,r);
}
int main()
{
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	in(n),in(n),in(c);
	while(c!=3)
	{
		if(c==1)
		{
			++t;
			o[t].t=t;
			in(o[t].x),in(o[t].y),in(o[t].w);
		}
		else if(c==2)
			add();
		in(c);
	}
	std::sort(o+1,o+t+1,comp);
	CDQ(1,t);
	for(int i=1;i<=ans[0];++i)
		printf("%d\n",ans[i]);
	//while(1);
}