记录编号	88398	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	蒟蒻mhr	是否通过	通过
代码语言	C++	运行时间	3.543 s
提交时间	2014-02-20 17:42:18	内存使用	12.14 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

struct thi{int x1,y1,x2,y2,num,sign,ans;
}a[200010];

struct node{int sign,x,y1,y2,num,yuan;
}b[200010];

int t[500010];
int w,n;

void add(int x,int y){for(x;x<=w;x+=x&-x)t[x]+=y;}
int ask(int x){int ans=0;for(x;x;x-=x&-x)ans+=t[x];return ans;}

bool cmp(node x,node y)
{
	if(x.x<y.x)return 1;
	if(x.x>y.x)return 0;
	if(x.sign==2)return 0;
	if(y.sign==2)return 1;
	return 1;
}

void solve(int l,int r)
{
	if(l==r)return;
	int i,j,k,mid=(l+r)/2,cnt=0;
	for(i=l;i<=mid;i++)
		if(a[i].sign==1)
			b[++cnt].sign=1,b[cnt].x=a[i].x1,b[cnt].y1=a[i].y1,b[cnt].num=a[i].num;
	for(i=mid+1;i<=r;i++)
		if(a[i].sign==2)
			b[++cnt].sign=2,b[cnt].x=a[i].x1-1,b[cnt].y1=a[i].y1,b[cnt].y2=a[i].y2,b[cnt].yuan=i,
			b[++cnt].sign=2,b[cnt].x=a[i].x2,b[cnt].y1=a[i].y1,b[cnt].y2=a[i].y2,b[cnt].yuan=i;
	sort(b+1,b+cnt+1,cmp);
	for(i=1;i<=cnt;i++)
		if(b[i].sign==1)
			add(b[i].y1,b[i].num);
		else
		{
			j=ask(b[i].y2)-ask(b[i].y1-1);
			if(b[i].x==a[b[i].yuan].x1-1)a[b[i].yuan].ans-=j;
			else a[b[i].yuan].ans+=j;
		}
	for(i=1;i<=cnt;i++)
		if(b[i].sign==1)
			add(b[i].y1,-b[i].num);
	solve(l,mid);solve(mid+1,r);
}

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