记录编号	188519	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	2.311 s
提交时间	2015-09-23 19:27:32	内存使用	15.58 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
    char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -1;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<3) + (x<<1) + (c-'0');
    x *= flag;
}
template<class Num>void write(Num x)
{
    if(!x) {putchar('0');return;}
    if(x < 0) putchar('-'), x = -x;
    static char s[20];int sl = 0;
    while(x) s[sl++] = x%10 + '0',x /= 10;
    while(sl) putchar(s[--sl]);
}

const int maxW = 2e6 + 50, maxn = 200050;

struct factor
{
	int t, x, y, a;
	factor(int t = 0,int x = 0,int y = 0,int a = 0):t(t), x(x), y(y), a(a){}
}fac[maxn];

int W, sz, op_sz;
long long ans[maxn];
int bit[maxW];

#define lowbit(x) ((x)&(-x))
void add(int p,int v)
{
	while(p <= W)
	{
		bit[p] += v;
		p += lowbit(p);
	}
}
int count(int p)
{
	int ret = 0;
	while(p > 0)
	{
		ret += bit[p];
		p -= lowbit(p);
	}
	return ret;
}

void solve(int l,int r)
{
	static factor arr[maxn];
	
	if(l >= r) return;
	
	int mid = (l + r) >> 1;
		
	solve(l, mid), solve(mid + 1, r);
	
	int j = l;
	
	for(int i = mid + 1; i <= r; i++)
		if(abs(fac[i].t) == 2)
		{
			while(j <= mid && fac[j].x <= fac[i].x)
			{
				if(fac[j].t == 1) add(fac[j].y, fac[j].a);
				j++;
			}
			if(fac[i].t > 0) ans[fac[i].a] += count(fac[i].y);
			else ans[fac[i].a] -= count(fac[i].y);
		}
		
	while(j > l)
	{
		--j;
		if(fac[j].t == 1) add(fac[j].y, -fac[j].a);	
	}
	
	int p = l, q = mid + 1, s = 0;
	while(p <= mid && q <= r)
	{
		if(fac[p].x <= fac[q].x)
			arr[s++] = fac[p], p++;
		else
			arr[s++] = fac[q], q++;
	}
	
	while(p <= mid) arr[s++] = fac[p], p++;
	while(q <= r) arr[s++] = fac[q], q++;
	
	for(int i = 0; i <= r - l; i++)
		fac[l + i] = arr[i];
}

int main()
{
	int op, x, y, a, b;
	
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);

	while(true)
	{
		read(op);
		
		if(op == 0)
			read(W);
		else if(op == 1)
		{
			read(x), read(y), read(a);
			fac[++sz] = factor(1, x, y, a);
		}
		else if(op == 2)
		{
			++op_sz;
			read(x), read(y), read(a), read(b);
			fac[++sz] = factor(2, a, b, op_sz);
			fac[++sz] = factor(2, x - 1, y - 1, op_sz);
			fac[++sz] = factor(-2, a, y - 1, op_sz);
			fac[++sz] = factor(-2, x - 1, b, op_sz);
		}
		else
			break;
	}
	
	solve(1, sz);
	
	for(int i = 1; i <= op_sz; i++)
		write(ans[i]), puts("");
			
	fclose(stdin);
	fclose(stdout);

	return 0;
}