记录编号	41268	评测结果	AAAAAAAEEE
题目名称	[HAOI 2012]矩形覆盖a	最终得分	70
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	2.887 s
提交时间	2012-07-21 16:49:27	内存使用	0.32 MiB

#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=2222;
int N,M,K,f,x1,y1,x2,y2,ans;
class SegTree
{
	public:
		int L,R,Mid,Area,Wall;
		SegTree *lc,*rc;
		inline void clear()
		{
			L=0,R=0,Mid=0,Wall=0,Area=0;
			lc=NULL,rc=NULL;
		}
};
SegTree* Root[MAXN];

void build(SegTree *pnt,int l,int r)
{
	pnt->clear(); pnt->L=l,pnt->R=r;
	pnt->Mid=(l+r)/2; if(l==r) return;
	SegTree *Left=new SegTree;
	SegTree *Right=new SegTree;
	build(Left,l,pnt->Mid);
	build(Right,pnt->Mid+1,r);
	pnt->lc=Left; pnt->rc=Right;
	Right=NULL; Left=NULL;
	delete Right; delete Left;
}

void Insert(SegTree *pnt,int l,int r,bool flag)
{
	if(pnt->L==l && pnt->R==r)
	{
		if(flag) pnt->Wall++; else pnt->Wall--;
		if(pnt->Wall) pnt->Area=r-l+1;
		if(pnt->Wall==0)
		{
			if(l!=r) 
				pnt->Area=pnt->lc->Area+pnt->rc->Area;
			else pnt->Area=0;
		}
		return;
	}
	else if(r<=pnt->Mid) 
		Insert(pnt->lc,l,r,flag);
	else if(l>=pnt->Mid+1)
		Insert(pnt->rc,l,r,flag);
	else
	{
		Insert(pnt->lc,l,pnt->Mid,flag);
		Insert(pnt->rc,pnt->Mid+1,r,flag);
	}
	if(pnt->Wall==0) 
		pnt->Area=pnt->lc->Area+pnt->rc->Area;
}

int main()
{
	freopen("jxfgx.in","r",stdin);
	freopen("jxfgx.out","w",stdout);
	scanf("%d %d %d\n",&N,&M,&K);
	for(int i=1;i<=M;i++)
	{
		Root[i]=new SegTree;
		build(Root[i],1,N);
	}
	for(int i=1;i<=K;i++)
	{
		scanf("%d %d %d %d %d\n",&f,&x1,&y1,&x2,&y2);
		if(f==1) 
		{
			for(int j=y1;j<=y2;j++) 
				Insert(Root[j],x1,x2,1);
		}
		else 
		{
			for(int j=y1;j<=y2;j++) 
				Insert(Root[j],x1,x2,0);
		}
		ans=0;
		for(int j=1;j<=M;j++)
			ans+=Root[j]->Area;
		printf("%d\n",ans);	
	}
	return 0;
}