记录编号	370230	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	gls1196	是否通过	通过
代码语言	C++	运行时间	3.402 s
提交时间	2017-02-13 07:19:58	内存使用	13.29 MiB

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

const int maxn = 2000100;
const int maxm = 200010;
int n,m,cnt,N;
int T[maxn],Tmp[maxm],Ans[maxm];
int Query(int x){
	int res = 0;
	for(;x >= 1;x -= (x&-x))res += T[x];
	return res;
}
void Modify(int x,int w){
	for(;x <= n;x += (x&-x))T[x] += w;
}

struct Que{
	int px,py,val,flag,id;
}Q[maxm];
bool operator < (const Que &ra,const Que &rb){
	return ra.px < rb.px;
}
#define mid ((l+r)>>1)
void Solve(int l,int r){
	if(l == r)return;
	Solve(l,mid);
	Solve(mid+1,r);
	sort(Q+l,Q+mid+1);
	sort(Q+mid+1,Q+r+1);
	int L = l;cnt = 0;
	for(int i = mid+1;i <= r;++i){
		if(Q[i].flag == 2){
			while(L <= mid && Q[L].px <= Q[i].px){
				if(Q[L].flag == 1){
					Tmp[++cnt] = L;
					Modify(Q[L].py,Q[L].val);
				}
				L++;
			}
			Ans[Q[i].id] += Q[i].val*Query(Q[i].py);
		}
	}
	for(int i = 1;i <= cnt; ++i){
		Modify(Q[Tmp[i]].py,-Q[Tmp[i]].val);
	}
}
int main(){
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	scanf("%d%d",&m,&n);m = 0;
	int opt,x1,y1,x2,y2,w;
	N = 0;
	while(scanf("%d",&opt) , opt < 3){
		if(opt == 1){
			scanf("%d%d%d",&x1,&y1,&w);
			Q[++m] = (Que){x1,y1,w,1,0};
		}
		else{
			++N;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			Q[++m] = (Que){x2,y2,1,2,N};
			if(x1 > 1 && y1 > 1)Q[++m] = (Que){x1-1,y1-1,1,2,N};
			if(y1 > 1)Q[++m] = (Que){x2,y1-1,-1,2,N};
			if(x1 > 1)Q[++m] = (Que){x1-1,y2,-1,2,N};
		}
	}
	Solve(1,m);
	for(int i = 1;i <= N;++i){
		printf("%d\n",Ans[i]);
	}
//	while(1);
	return 0;
}