［线段树］ HDOJ Excited Database

#include 
using namespace std;
typedef long long LL;

#define now o, L, R, tree
#define lson o > 1;
		LL tl = mid-L+1, tr = R-mid;
		tree[ls].sum += (1 + tl) * tl / 2 * tree[o].lazy;
		tree[rs].sum += (1 + tr) * tr / 2 * tree[o].lazy;
		tree[ls].val += tl * tree[o].lazy;
		tree[rs].val += tr * tree[o].lazy;
		tree[ls].lazy += tree[o].lazy;
		tree[rs].lazy += tree[o].lazy;
		tree[o].lazy = 0;
	}
}

void pushup(int o, int L, int R, node tree[])
{
	int mid = (L + R) >> 1;
	tree[o].val = tree[ls].val + tree[rs].val;
	tree[o].sum = tree[ls].sum + tree[rs].sum + tree[rs].val * (mid-L+1);
}

void build(int o, int L, int R, node tree[])
{
	tree[o].sum = tree[o].val = tree[o].lazy = 0;
	if(L == R) return;
	int mid = (L + R) >> 1;
	build(lson);
	build(rson);
	pushup(now);
}

void update(int o, int L, int R, node tree[], int ql, int qr)
{
	if(ql = R) {
		LL len = R - L + 1;
		tree[o].lazy += 1;
		tree[o].val += len;
		tree[o].sum += (1 + len) * len / 2;
		return;
	}
	pushdown(now);
	int mid = (L + R) >> 1;
	if(ql  mid) update(rson, ql, qr);
	pushup(now);
}

node query(int o, int L, int R, node tree[], int ql, int qr)
{
	if(ql = R) return tree[o];
	pushdown(now);
	int mid = (L + R) >> 1;
	node ans;
	if(qr  mid) ans = query(rson, ql, qr);
	else {
		ans = query(lson, ql, qr);
		node t = query(rson, ql, qr);
		ans.val += t.val;
		ans.sum += t.sum;
		ans.sum += (mid - max(ql, L) + 1) * t.val;
	}
	pushup(now);
	return ans;
}

LL solve2(int ql, int qr)
{
	ql += n, qr += n;
	node ans = query(1, 1, 2 * n, b, ql, qr);
	return ans.sum;
}

LL solve1(int ql, int qr)
{
	node ans = query(1, 1, 2 * n, a, ql, qr);
	return ans.sum;
}

void solve()
{
	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
	
	LL ans = 0;
	ans += solve2(x1 - y2, x2 - y1);
	ans -= solve2(x1 - y1 + 1, x2 - y1);
	ans -= solve2(x2 - y2 + 1, x2 - y1);
	
	ans += solve1(x1 + y1, x2 + y2);
	ans -= solve1(x2 + y1 + 1, x2 + y2);
	ans -= solve1(x1 + y2 + 1, x2 + y2);
	printf("%lldn", ans);
}

void work()
{
	scanf("%d%d", &n, &m);
	build(1, 1, 2 * n, a);
	build(1, 1, 2 * n, b);
	
	while(m--) {
		int op;
		scanf("%d", &op);
		if(op == 1) {
			int ql, qr;
			scanf("%d%d", &ql, &qr);
			update(1, 1, 2 * n, a, ql, qr);
		}
		
		if(op == 2) {
			int ql, qr;
			scanf("%d%d", &ql, &qr);
			ql += n, qr += n;
			update(1, 1, 2 * n, b, ql, qr);
		}
		
		if(op == 3) solve();
	}
}

int main()
{
	int _;
	scanf("%d", &_);
	for(int i = 1; i