记录编号	563536	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	zxsoul	是否通过	通过
代码语言	C++	运行时间	3.774 s
提交时间	2021-08-20 07:34:07	内存使用	100.28 MiB

/*
/*
	对于弱化版 利用扫描线去做，
	对于每一列都是先修改后查询，
	
	问题：
		扫描线怎么写
		怎么扫描线哇，怎么保证先修改后查询
		重叠的问题
		为什么排序，
		层层之间为什么独立 
		
	扫描线并不是我想象中的
	大体流程：
	先分成两份区间，在左区间找到可以做出贡献的值，在右区间查询的值。
	然后再进行排序，按顺序依次先更新在求和，这里详细的求和拆分成前缀的形式得到前缀和，每个点i表示i行的前缀，而前面指的前缀和是列，这样刚好是一个二位前缀和
	 
	还原的原因，也就是重叠的情况的分析，对于一个矩形统计答案是用树状数组前缀和的形式，首先明确一点，我们对于当前这一层，是对某一询问进行更新，即加值或者减值，这个操作我们怎么实现
	树状数组前缀和，如果上一层的值还留在树状数组中，所求答案必然不是正确的，因为扫描线只有一条，在上一层中是一扫到最后，此时的树状数组中已经存了前面所有的更新，换句话话，现在的树状数组只对上一层的最后一个询问可以得到正确答案，如果
	不清零，在继续重新从头开始，这个树状数组不是空的，含有上一层的信息，而层与层之间是独立的，所以清零

	层层之间为什么相互独立 因为保证的答案不重叠，一层的修改对应到后面的询问已经做过贡献了，而扫描线就一条，所以如果不清零就再次使用扫描线，这必然会算重。所以层层之间相互独立	 
	
	排序的原因是，在一层中，我们要在合适的时间复杂度内完成前半部分的修改去影响后半部分的询问，那么我们按照坐标排序，一次行的完成查询的修改 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int B=2*1e6+10;
struct node{int opt,x1,y1,x2,y2,id,v;} a[B],cc[B];
int cnt=0;
int cmp(node a,node b)
{
	if (a.x1==b.x1) return a.opt<b.opt;
	return a.x1<b.x1;
}
int read() {int x; scanf("%d",&x);return x;}
int n;
int m;
int t[B];
int lowbit(int x) {return x&(-x);}
void modify(int x,int v) {while (x<=n) t[ x]+=v,x+=lowbit(x);}
int query(int x) {int res=0; while (x>0) res+=t[x],x-=lowbit(x);return res;}//注意这是>0 
int ans[B];
void solve(int l,int r)
{
	if (l==r) return;
	cnt=0;//记录做区间需要修改的点 
	int mid=l+r>>1;
	for (int i=l;i<=mid;i++) 
		if (a[i].opt==0) 
		{
			cc[++cnt]=a[i];//得到左区间内需要修改的点 
		}
	for (int i=mid+1;i<=r;i++)
	{
		if (a[i].opt==1)
		{//是查询点 
			cc[++cnt]=a[i];
			cc[++cnt]=a[i];
			cc[cnt-1].x1--;
			cc[cnt].x1=cc[cnt].x2;//这个地方因为我是从1开始的，所以前一个和前两个分别是cnt cnt-1 而不是cnt-1,cnt-2. 
			cc[cnt].opt=2;
		}
	}
	sort(cc+1,cc+1+cnt,cmp);
	for (int i=1;i<=cnt;i++)
	{
		if (cc[i].opt==0) modify(cc[i].y1,cc[i].v);
		else if (cc[i].opt==1)
		{
			ans[cc[i].id]-=query(cc[i].y2)-query(cc[i].y1-1);	
		}
		else if (cc[i].opt==2)
		{
			ans[cc[i].id]+=query(cc[i].y2)-query(cc[i].y1-1);	
		}
	}
	for (int i=1;i<=cnt;i++)
	{
		if (cc[i].opt==0) modify(cc[i].y1,-cc[i].v);//还原，保持层层之间相互独立 
	}
	solve(l,mid),solve(mid+1,r);
} 
int main()
{
	freopen("locust.in","r",stdin);
	freopen("locust.out","w",stdout);
	n=read(); m=read();
	for (int i=1;i<=m;i++)
	{
		a[i].opt=read()-1; 
		if (a[i].opt==0) {a[i].x1=read(),a[i].y1=read(),a[i].v=read(),a[i].id=i;}
		else 
		{
			int x1=read(),y1=read(),x2=read(),y2=read();
			a[i].x1=min(x1,x2);
			a[i].x2=max(x1,x2);
			a[i].y1=min(y1,y2);
			a[i].y2=max(y1,y2);
			a[i].id=i;
		}
	}
	solve(1,m);
	for (int i=1;i<=m;i++)
	{
		if (a[i].opt==1) printf("%d\n",ans[i]);
	}
}
/*
5
8
2 4 1 4 2
1 3 1 8
1 4 4 4
2 1 3 4 4
1 1 5 1
1 4 4 5
2 2 2 5 4
2 3 2 4 4
*/