记录编号	276432	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	沉迷学习的假的Keller	是否通过	通过
代码语言	C++	运行时间	2.539 s
提交时间	2016-07-03 21:31:36	内存使用	14.37 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=200005;
struct work{
	int x1,y1,x2,y2,op,k,num;
	int ans;
}p[maxn],cc[maxn<<1];
int c[500005];
int w,n;

inline int in(){
	int TEMP,EPX;
	TEMP=0;EPX=getchar();
	while(EPX<48||EPX>57)
		EPX=getchar();
	for(;EPX>47&&EPX<58;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+EPX-48;
	return TEMP;
}

//树状数组 ***************
int lowbit(int x){
	return x&(-x);
}

void add(int x,int k){
	for(int i=x;i<=w;i+=lowbit(i)){
		c[i]+=k;
	}
}

int sum(int x){
	int q=0;
	for(int i=x;i;i-=lowbit(i)){
		q+=c[i];	
	}
	return q;
}
//************************

bool cmp(const work&a,const work&b){
	if(a.x1==b.x1) return a.op<b.op;
	return a.x1<b.x1;	
}

void solve(int l,int r){   //CDQ分治 
	if(l==r) return;
	int mid=(l+r)>>1;
	//printf("%d%d\n",l,r);
	int cnt=0;
	for(int i=l;i<=mid;i++){   // (l,mid)区间中修改操作 
		if(p[i].op==1)
			cc[cnt++]=p[i];	
	}
	for(int i=mid+1;i<=r;i++){  //  (mid+1,r)区间中查询操作 
		if(p[i].op==2){
			cc[cnt++]=p[i];
			cc[cnt++]=p[i];
			cc[cnt-2].x1--;        //查询时需要用 x2的值减x1-1的值是区间(x1,x2) 的值 
			cc[cnt-1].x1=p[i].x2;
			cc[cnt-1].op=3;
		}
	}
	sort(cc,cc+cnt,cmp);  //根据x轴排序 
	for(int i=0;i<cnt;i++){
		if(cc[i].op==1){
			add(cc[i].y1,cc[i].k);	 //修改 
		}
		else if(cc[i].op==2){
			p[cc[i].num].ans -= sum(cc[i].y2)-sum(cc[i].y1-1);   // x1-1前的修改值 
		}
		else {
			p[cc[i].num].ans += sum(cc[i].y2)-sum(cc[i].y1-1);	// x2前的修改值 
		}
	}
	for(int i=0;i<cnt;i++){
		if(cc[i].op==1){
			add(cc[i].y1,-cc[i].k);	   //清空c树状数组 
		}
	}
	solve(l,mid);
	solve(mid+1,r);          //分治 
	return ;
}

int MAIN(){
	freopen("locust.in","r",stdin);
	freopen("locust.out","w",stdout);
	scanf("%d %d",&w,&n);
	int flag,a,b,c,d;
	for(int i=1;i<=n;i++){
		//scanf("%d",&flag);
		flag=in();
		if(flag==1){
			//scanf("%d%d%d",&a,&b,&c);
			a=in();b=in();c=in();
			p[i].op=1;
			p[i].x1=a;
			p[i].y1=b;
			p[i].k=c;
		}else{
			//scanf("%d%d%d%d",&a,&b,&c,&d);
			a=in();b=in();c=in();d=in();
			p[i].op=2;
			p[i].x1=min(a,c);
			p[i].y1=min(b,d);
			p[i].x2=max(a,c);
			p[i].y2=max(b,d);
		}
		p[i].num=i;
	}
	solve(1,n);
	for(int i=1;i<=n;i++){
		if(p[i].op==2) printf("%d\n",p[i].ans);	
	}
	return 0;
}
int main(){;}
int helenkeller=MAIN();