比赛 20161116 评测结果 AAAAAAAAAA
题目名称 删除他们! 最终得分 100
用户昵称 cwm大佬%%% 运行时间 1.684 s
代码语言 C++ 内存使用 53.70 MiB
提交时间 2016-11-16 10:23:57
显示代码纯文本
#include<cstdio>

const int NM=1000000+10;

int n,m,q;

struct SEG{
	struct P{
		bool pudown;
		int delta,sum;
		int l,r;
		int lc,rc;
	};
	P tree[NM*2];
	int top;
	SEG(){top=0;}
	int build_tree(int l,int r){
		int p=top++;
		P &now=tree[p];
		now=(P){0,0,0,l,r,-1,-1};
		if(l<r){
			now.lc=build_tree(l,(l+r)/2);
			now.rc=build_tree((l+r)/2+1,r);
		}
		return p;
	}
	void push_down(int p){
		P &now=tree[p];
		if(now.pudown==0)return;
		tree[now.lc].pudown=1;
		tree[now.lc].delta=now.delta;
		tree[now.lc].sum=now.delta*(tree[now.lc].r-tree[now.lc].l+1);
		tree[now.rc].pudown=1;
		tree[now.rc].delta=now.delta;
		tree[now.rc].sum=now.delta*(tree[now.rc].r-tree[now.rc].l+1);
		now.sum=tree[now.lc].sum+tree[now.rc].sum;
		now.pudown=0;
	}
	void change(int l,int r,int delta,int p=0){
		if(p==-1)return;
		P &now=tree[p];
		if(now.l>r||now.r<l)return;
		if(now.l>=l&&now.r<=r){
			now.pudown=1;
			now.delta=delta;
			now.sum=now.delta*(now.r-now.l+1);
		}else{
			push_down(p);
			change(l,r,delta,now.lc);
			change(l,r,delta,now.rc);
			now.sum=tree[now.lc].sum+tree[now.rc].sum;
		}
	}
	int query(int l,int r,int p=0){
		if(p==-1)return 0;
		P &now=tree[p];
		if(now.l>r||now.r<l)return 0;
		if(now.l>=l&&now.r<=r)return now.sum;
		push_down(p);
		return query(l,r,now.lc)+query(l,r,now.rc);
	}
	//void put(){for(int i=0;i<top;i++)printf("%d %d : %d %d %d\n",tree[i].l,tree[i].r,tree[i].pudown,tree[i].delta,tree[i].sum);putchar('\n');}
};
SEG G;

int hash(int x,int y){return x*m+y;}
void _hash(int sum,int &x,int &y){
	y=sum%m;
	x=sum/m;
}

int main()
{
	freopen("deleteit.in","r",stdin);
	freopen("deleteit.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	G.build_tree(0,n*m-1);
	G.change(0,m*n-1,1);
	for(int i=0;i<q;i++){
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		for(int i=x1;i<=x2;i++)G.change(hash(i,y1),hash(i,y2),0);
		int tot=G.query(hash(x1,y1),n*m-1);
		G.change(hash(x1,y1),n*m-1,0);
		G.change(hash(x1,y1),hash(x1,y1)+tot-1,1);
	}
	printf("%d\n",G.query(0,m*n-1));
	return 0;
}