记录编号	369138	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	2.454 s
提交时间	2017-02-08 10:11:03	内存使用	47.61 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAXN 2000001
#define MAXX 800000

inline void read(int &x) {
	char c;bool flag(0);
	while((c = getchar())<'0' || c>'9') if(c=='-') flag = 1;
	x = c - '0';
	while((c = getchar())>='0' && c<='9') x = x*10+c-'0';
	if (flag) x = -x;
}

struct Que {
	int x,y,v,cas,t,pos;
	Que(int x,int y,int v,int cas,int t,int pos):x(x),y(y),v(v),cas(cas),t(t),pos(pos){}
	Que(){}
	void out(){printf("X:%d, y:%d, v:%d, cas:%d, t:%d, pos:%d\n",x,y,v,cas,t,pos);}
	bool operator < (const Que &lhs) const{return x < lhs.x;}
}q[MAXX],t[MAXX];

int ans[MAXX],S[MAXN];
int w,tot = 0,pos = 0;

int Add(int p,int x){for (; p <= w; p += p&-p) S[p] += x;}

int Sum(int p,int ans = 0){for (; p; p -= p&-p)ans += S[p]; return ans;}

void cdq(int l,int r) {
	if(l == r) return;
	int mid = l+r>>1,s = l,a = l,b = mid+1;
	for (int i = l; i <= r; i++)
	  q[i].t<=mid ? t[a++]=q[i] : t[b++]=q[i];
	for (int i = l; i <= r; i++) q[i] = t[i];
	int j = l;
	for (int i = mid+1; i <= r; i++)
	  if(q[i].cas) {
		for ( ;j<=mid && q[j].x<=q[i].x; j++)
		  if (!q[j].cas) Add(q[j].y,q[j].v);
		ans[q[i].pos] += q[i].cas*Sum(q[i].y);
	}
	for (int i = l; i < j; i++)
	  if(!q[i].cas) Add(q[i].y,-q[i].v);
	cdq(l,mid); cdq(mid+1,r);
}

void init() {
	getchar(); read(w);
	int qc,x,y,xx,yy,v,t = 0;
	while(read(qc),qc != 3) {
		read(x);read(y);
		if(qc == 1) {
			read(v);
			q[++tot] = Que(x,y,v,0,tot,0);
		} else {
			read(xx); read(yy);
			q[++tot] = Que(xx,yy,0,1,tot,++pos);
			q[++tot] = Que(x-1,y-1,0,1,tot,pos);
			q[++tot] = Que(x-1,yy,0,-1,tot,pos);
			q[++tot] = Que(xx,y-1,0,-1,tot,pos);
		}
	}
}

int main() {
	freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    init();
    sort(q+1,q+tot+1);
    //for (int i = 1; i <= tot; i++) q[i].out();
    cdq(1,tot);
    for (int i = 1; i <= pos; i++) printf("%d\n",ans[i]);
}