记录编号	95811	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[OIBH 练习赛#6]战地统计系统	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	7.547 s
提交时间	2014-04-09 08:45:24	内存使用	166.48 MiB

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>

using namespace std;

const int MAXN=1000+100;

int N=0;

struct rec{
	int x1,y1,x2,y2;//左上角坐标和右下角坐标
	rec(int x11,int y11,int x22,int y22):x1(x11),y1(y11),x2(x22),y2(y22){}
	rec():x1(0),y1(0),x2(0),y2(0){}
};

int cal_size(rec r){
	return (abs(r.x2-r.x1)+1)*(abs(r.y2-r.y1)+1);
}

bool is_same(rec r1,rec r2){
	return 	r1.x1==r2.x1 && 
			r1.x2==r2.x2 &&
			r1.y1==r2.y1 &&
			r1.y2==r2.y2;
}

bool int_rec(rec r1,rec r2,rec & int_r){
	
	if(r1.x1>r2.x1)swap(r1,r2);//按左上角坐标从左到右拍
	if(r2.x1<=r1.x2){
		int_r.x1=r2.x1;
		int_r.x2=min(r1.x2,r2.x2); 
	}else{
		return false;
	}
	
	if(r1.y1>r2.y1)swap(r1,r2);//按左上角坐标从左到右拍
	if(r2.y1<=r1.y2){
		int_r.y1=r2.y1;
		int_r.y2=min(r1.y2,r2.y2); 
	}else{
		return false;
	}
	
	return true;
}

struct node{
	rec own_rec;//自己的区域 
	int left_s,right_s;
	int sum;
	int lazy;
	bool clr;
	node():left_s(-1),right_s(-1),sum(0),lazy(0),clr(false){}
	//void init():left_s(-1),right_s(-1),sum(0),lazy(0),clr(false){}
}nodes[MAXN*MAXN*4];

struct rec_tree{
	int node_tot;
	rec_tree():node_tot(0){}
	
	void push_down_clr(int x){
		node &now=nodes[x];
		now.sum=now.clr=now.lazy=0;
		if(now.left_s!=-1){ 
			nodes[now.left_s].clr=true;
		}
		if(now.right_s!=-1){ 
			nodes[now.right_s].clr=true;
		}
	}
	
	void push_down(int x){
		node &now=nodes[x];
		if(now.clr){
			push_down_clr(x);
		}
		if(now.left_s!=-1){ 
			if(nodes[now.left_s].clr){
				push_down_clr(now.left_s);
			}
			nodes[now.left_s].sum+=now.lazy*cal_size(nodes[now.left_s].own_rec);
			nodes[now.left_s].lazy+=now.lazy;
		}
		if(now.right_s!=-1){ 
			if(nodes[now.right_s].clr){
				push_down_clr(now.right_s);
			}
			nodes[now.right_s].sum+=now.lazy*cal_size(nodes[now.right_s].own_rec);
			nodes[now.right_s].lazy+=now.lazy;
		}
		now.lazy=0;
	}
	
	void insert(int x,rec inc_rec){
		push_down(x);//在增加前先把残局clr赶紧,再增加,要不然会影响lazy增加 
		node &now=nodes[x];
		now.sum+=cal_size(inc_rec);
		if(is_same(now.own_rec,inc_rec)){
			now.lazy+=1;
			return;
		}
		rec son_rec;
		if(now.left_s != -1 && int_rec(nodes[now.left_s].own_rec,inc_rec,son_rec)){
			insert(now.left_s,son_rec);
		}
		if(now.right_s != -1 && int_rec(nodes[now.right_s].own_rec,inc_rec,son_rec)){
			insert(now.right_s,son_rec);
		}
	}
	
	int delete_(int x,rec del_rec){
		push_down(x);
		node &now=nodes[x];
		int ans=0;
		if(is_same(now.own_rec,del_rec)){
			now.clr=true;
			ans=now.sum;
			push_down(x);
			return ans;
		}
		rec son_rec;
		if(now.left_s != -1 && int_rec(nodes[now.left_s].own_rec,del_rec,son_rec)){
			ans+=delete_(now.left_s,son_rec);
		}
		if(now.right_s != -1 && int_rec(nodes[now.right_s].own_rec,del_rec,son_rec)){
			ans+=delete_(now.right_s,son_rec);
		}
		now.sum-=ans;
		return ans;
	}
	
	int test(int x,rec del_rec){
		push_down(x);
		node &now=nodes[x];
		int ans=0;
		if(is_same(now.own_rec,del_rec)){
			//now.clr=true;
			ans=now.sum;
			push_down(x);
			return ans;
		}
		rec son_rec;
		if(now.left_s != -1 && int_rec(nodes[now.left_s].own_rec,del_rec,son_rec)){
			ans+=test(now.left_s,son_rec);
		}
		if(now.right_s != -1 && int_rec(nodes[now.right_s].own_rec,del_rec,son_rec)){
			ans+=test(now.right_s,son_rec);
		}
		return ans;
	}
	
	void build_tree(int x,rec bul_rec){
		node & now=nodes[x];
		//now.init();
		
		now.own_rec=bul_rec;
		
		if(cal_size(bul_rec)==1)return;
		
		rec l_c,r_c;
		int chang=abs(bul_rec.x2-bul_rec.x1)+1,kuan=abs(bul_rec.y2-bul_rec.y1)+1;
		
		if(chang>kuan){
			int mid=chang/2;
			l_c=rec(bul_rec.x1,bul_rec.y1 , bul_rec.x1+mid-1,bul_rec.y2);
			r_c=rec(bul_rec.x1+mid,bul_rec.y1 , bul_rec.x2,bul_rec.y2);
		}else{
			int mid=kuan/2;
			l_c=rec(bul_rec.x1,bul_rec.y1 , bul_rec.x2,bul_rec.y1+mid-1);
			r_c=rec(bul_rec.x1,bul_rec.y1+mid , bul_rec.x2,bul_rec.y2);
		}
		
		now.left_s=++node_tot;
		now.right_s=++node_tot;
		
		build_tree(now.left_s,l_c);
		build_tree(now.right_s,r_c);
		
	}
	
}solver;

void sol_t1(int left_p,int right_p,int v){
	solver.insert(0,rec(left_p,1,right_p,v));
}

void sol_t2(int left_p,int right_p,int v){
	int the_num_of_delete=solver.delete_(0,rec(left_p,1,right_p,v));
	printf("%d\n",the_num_of_delete);
}

void test(int n,int m){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<solver.test(0,rec(j,i,j,i))<<"\t";
		}
		cout<<endl;
	}
	cout<<"========"<<endl;
}

void solve(int type,int left_p,int right_p,int v){
	switch(type){
		case 1:
			sol_t1(left_p,right_p,v);
			break;
		case 2:
			sol_t2(left_p,right_p,v);
			break;
	}
	//test(10,10);
}

void get_inf(int &type,int &left_p,int &right_p,int &v){
	scanf("%d %d %d %d",&type,&left_p,&right_p,&v);
}

void work(){
	scanf("%d",&N);
	solver.build_tree(0,rec(1,1,MAXN,MAXN));///////
	int inf_num;scanf("%d",&inf_num);
	for(int i=1;i<=inf_num;i++){
		int type,left_p,right_p,v;
		get_inf(type,left_p,right_p,v);
		solve(type,left_p,right_p,v);
	}
}

void open(){
	//freopen("in.txt","r",stdin);
	freopen("battlefieldstat.in","r",stdin);
	freopen("battlefieldstat.out","w",stdout);
}

int main(){
	open();
	work();
	return 0;
}