记录编号	146982	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	3.957 s
提交时间	2015-01-21 22:15:32	内存使用	31.57 MiB

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <ctime>
inline void getd(int &x){
	char ch = getchar();
	while(!isdigit(ch))ch = getchar();
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 - '0' + ch;
}
/********************************************/
using namespace std;
const int maxn = 200003, maxw = 500003;

struct OPT{
	bool NotQ;//1:Add;0:Query
	int val, x, y, T;
	operator int ()const{return x;}
	inline void init(int a, int b, int c, int t){
		x = a, y = b, val = c, T = t;
		NotQ = 1;
	}
	inline void init(int a, int b, int t){
		x = a, y = b, val = 0, T = t;
		NotQ = 0;
	}
}Opt[maxn<<2], *opt[maxn<<2], *Begin[maxn];

struct Fenwick{
	#define lowbit(x) (x & -x)
	int len, A[maxn<<2], ind[maxn<<2], cnt;
	inline void init(int l){len = l;memset(A, 0, sizeof(int) * (len + 1));}
	inline void getind(OPT **L, OPT **R){
		static int tmp[maxn<<2], i;i = 0;cnt = 1;
		while(L < R){tmp[i++] = (*L)->y;++L;}
		sort(tmp, tmp + len);
		ind[cnt] = tmp[0];
		for(i = 1;i < len;++i)
			if(tmp[i] != ind[cnt])ind[++cnt] = tmp[i];
		++cnt;
	}
	inline void Add(int i, int x){
		i = lower_bound(ind + 1, ind + cnt, i) - ind;
		while(i <= len){
			A[i] += x;
			i += lowbit(i);
		}
	}
	inline int Sum(int i){
		i = lower_bound(ind + 1, ind + cnt, i) - ind;
		int ans = 0;
		while(i){
			ans += A[i];
			i ^= lowbit(i);
		}
		return ans;
	}
}F;

int W, N, Qcnt = 0, End;

inline void init(){
	getd(W), getd(N);
	int i, j, t, a, b, c, d;
	for(i = 0,j = 0;i < N;++i){
		getd(t);
		getd(a), getd(b), getd(c);
		if(t == 1){(opt[j] = Opt + j)->init(a, b, c, j);++j;}
		else{
			getd(d);
			Begin[Qcnt++] = Opt + j;
			(opt[j] = Opt + j)->init(a-1, b-1, j);++j;
			(opt[j] = Opt + j)->init(a-1, d, j);++j;
			(opt[j] = Opt + j)->init(c, b-1, j);++j;
			(opt[j] = Opt + j)->init(c, d, j);++j;
		}
	}
	End = j;
}

inline void Solve(int L, int R){
	static OPT *tmp[maxn<<2];
	int len = R - L, mid;
	OPT **it1, **it2;
	if(len == 1)return;
	mid = (L + R) >> 1, it1 = opt + L, it2 = opt + mid;
	if(len == 2){
		if(**it1 > **it2)swap(*it1, *it2);
		else if((*it2)->NotQ==0 && (*it1)->NotQ && (*it1)->y <= (*it2)->y)
			(*it2)->val += (*it1)->val;
		return;
	}
	Solve(L, mid);Solve(mid, R);
	OPT **m = opt + mid, **end = opt + R;
	for(int i = 0;i < len;++i){//merge sort
		if(it1 == m)tmp[i] = *(it2++);
		else if(it2 == end)tmp[i] = *(it1++);
		else if(**it1 > **it2)tmp[i] = *(it2++);
		else tmp[i] = *(it1++);
	}
	it1 = opt + L;
	F.init(len);
	F.getind(tmp, tmp + len);
	for(int i = 0;i < len;++i,++it1){
		*it1 = tmp[i];
		if((*it1)->T < mid && (*it1)->NotQ)
			F.Add((*it1)->y, (*it1)->val);
		else if((*it1)->T >= mid && !(*it1)->NotQ)
			(*it1)->val += F.Sum((*it1)->y);
	}
}

int main(){
	#ifdef DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("locust.in", "r", stdin);
	freopen("locust.out", "w", stdout);
	#endif
	init();
	Solve(0, End);
	int a, b, c, d;
	OPT **it = Begin;
	for(int i = 0;i < Qcnt;++i,++it){
		a = (*it)->val;
		b = (*it+1)->val;
		c = (*it+2)->val;
		d = (*it+3)->val;
		printf("%d\n", a - b - c + d);
	}
	
	return 0;
}