记录编号	95569	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[OIBH 练习赛#6]战地统计系统	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.609 s
提交时间	2014-04-07 19:04:12	内存使用	78.17 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=1010,SIZEM=2010;
class NODE{
public:
	int x1,y1,x2,y2;//左下角和右上角,包含整个闭区间
	int size;
	int lc,rc;//左右儿子
	int lazy;
	bool clr;//是否被清除,这个排在lazy前面,切记不能用sum判断是否清空
	int sum;//部队数量,如果是0代表该区域已清空
	//clear可以清空lazy,反之不行
	void clear(void){sum=lazy=0;clr=true;}
};
NODE tree[SIZEN*SIZEN*2];
int tot=0;
int build(int x1,int y1,int x2,int y2){
	int p=tot++;
	NODE &now=tree[p];
	now.x1=x1,now.y1=y1,now.x2=x2,now.y2=y2;
	now.size=(x2-x1+1)*(y2-y1+1);
	now.lazy=now.clr=now.sum=0;
	if(x1<x2||y1<y2){
		if(x2-x1>=y2-y1){
			int xm=(x1+x2)/2;
			now.lc=build(x1,y1,xm,y2);
			now.rc=build(xm+1,y1,x2,y2);
		}
		else{
			int ym=(y1+y2)/2;
			now.lc=build(x1,y1,x2,ym);
			now.rc=build(x1,ym+1,x2,y2);
		}
	}
	else now.lc=now.rc=-1;
	return p;
}
void update(int root){
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.lc==-1){
		now.clr=(!now.sum);
		return;
	}
	NODE &lson=tree[now.lc],&rson=tree[now.rc];
	now.sum=lson.sum+rson.sum;
	//两个lazy标记都不能update
}
void pushdown(int root){
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.lc==-1) return;
	NODE &lson=tree[now.lc],&rson=tree[now.rc];
	if(now.clr){//清空,这个操作先于lazy
		lson.clear();
		rson.clear();
		now.clr=false;
	}
	if(now.lazy){
		NODE &lson=tree[now.lc],&rson=tree[now.rc];
		lson.lazy+=now.lazy,rson.lazy+=now.lazy;
		lson.sum+=now.lazy*lson.size,rson.sum+=now.lazy*rson.size;
		now.lazy=0;
	}
}
int fire(int root,int x1,int y1,int x2,int y2){//返回区域内军队数量,并把它们干掉
	pushdown(root);
	NODE &now=tree[root];
	if(now.x1>x2||now.x2<x1||now.y1>y2||now.y2<y1) return 0;
	if(now.x1>=x1&&now.x2<=x2&&now.y1>=y1&&now.y2<=y2){
		int ans=now.sum;
		now.clear();//之前的lazy必须清除
		return ans;
	}
	else{
		int ans=fire(now.lc,x1,y1,x2,y2)+fire(now.rc,x1,y1,x2,y2);
		update(root);
		return ans;
	}
}
void add(int root,int x1,int y1,int x2,int y2,int t){//范围内每格加t
	pushdown(root);
	NODE &now=tree[root];
	if(now.x1>x2||now.x2<x1||now.y1>y2||now.y2<y1) return;
	if(now.x1>=x1&&now.x2<=x2&&now.y1>=y1&&now.y2<=y2){
		now.lazy+=t;
		now.sum+=t*now.size;
	}
	else{
		add(now.lc,x1,y1,x2,y2,t);
		add(now.rc,x1,y1,x2,y2,t);
		update(root);
	}
}
int N,M,maxV=0;
int K[SIZEM]={0},X1[SIZEM]={0},X2[SIZEM]={0},V[SIZEM]={0};
void work(void){
	for(int i=1;i<=M;i++){
		if(K[i]==1){//增援
			add(0,X1[i],1,X2[i],V[i],1);
		}
		else{
			printf("%d\n",fire(0,X1[i],1,X2[i],V[i]));
		}
	}
}
void init(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		scanf("%d%d%d%d",&K[i],&X1[i],&X2[i],&V[i]);
		maxV=max(maxV,V[i]);
	}
	build(1,1,N,maxV);
}
int main(){
	freopen("battlefieldstat.in","r",stdin);
	freopen("battlefieldstat.out","w",stdout);
	init();
	work();
	return 0;
}