比赛 20120721 评测结果 AAAATTTEEE
题目名称 矩形覆盖a 最终得分 40
用户昵称 Makazeu 运行时间 3.763 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2012-07-21 11:28:44
显示代码纯文本
#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;
		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;
	pnt->lc=new SegTree;
	pnt->rc=new SegTree;
	build(pnt->lc,l,pnt->Mid);
	build(pnt->rc,pnt->Mid+1,r);
}

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

int Find(SegTree *pnt,int l,int r)
{
	if(pnt->L==r && pnt->R==r) 
		return pnt->Area;
	if(r<=pnt->Mid) return Find(pnt->lc,l,r);
	if(l>=pnt->Mid+1) return Find(pnt->rc,l,r);
	return Find(pnt->lc,l,pnt->Mid)+Find(pnt->rc,pnt->Mid+1,r);	
}

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+=Find(Root[j],1,N);
		printf("%d\n",ans);	
	}
	return 0;
}