poj 1195 Mobile phones

Problem

poj.org/problem?id=1195

vjudge.net/contest/146952#problem/C

Meaning

有一个 S * S 的正方形区域（两维的下标范围都是是 0 ~ S-1），有 4 种操作：

1. 0 S：读入区域边长，初始化每一个格的值为 0；

2. 1 X Y A：给下标为（X，Y）的点加上 A；

3. 2 L B R T：询问区域 { L <= X <= R，B <= Y <= T } 的总和；

4. 3：结束

Analysis

二维线段数的单点更新、查询模板题。

Code

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1024;

int tree[N<<1][N<<1], n;

inline void pushup_y(int x, int y)
{
	tree[x][y] = tree[x][y<<1] + tree[x][y<<1|1];
}

void pushup_x(int p, int l, int r, int x, int y)
{
	if(l != r)
	{
		int m = l + r >> 1;
		if(m < p)
			pushup_x(p, m+1, r, x, y<<1|1);
		else
			pushup_x(p, l, m, x, y<<1);
	}
	tree[x][y] = tree[x<<1][y] + tree[x<<1|1][y];
}

void update_y(int y, int v, int l, int r, int xid, int yid)
{
	if(l == r)
		tree[xid][yid] += v;
	else
	{
		int m = l + r >> 1;
		if(m < y)
			update_y(y, v, m+1, r, xid, yid<<1|1);
		else
			update_y(y, v, l, m, xid, yid<<1);
		pushup_y(xid, yid);
	}
}

void update_x(int x, int y, int v, int l, int r, int xid)
{
	if(l == r)
		update_y(y, v, 0, n-1, xid, 1);
	else
	{
		int m = l + r >> 1;
		if(m < x)
			update_x(x, y, v, m+1, r, xid<<1|1);
		else
			update_x(x, y, v, l, m, xid<<1);
		pushup_x(y, 0, n-1, xid, 1);
	}
}

int query_y(int yl, int yr, int l, int r, int xid, int yid)
{
	if(yl <= l && r <= yr)
		return tree[xid][yid];
	if(r < yl || yr < l)
		return 0;
	int m = l + r >> 1;
	return query_y(yl, yr, l, m, xid, yid<<1) +
		query_y(yl, yr, m+1, r, xid, yid<<1|1);
}

int query_x(int xl, int xr, int yl, int yr, int l, int r, int xid)
{
	if(xl <= l && r <= xr)
		return query_y(yl, yr, 0, n-1, xid, 1);
	if(r < xl || xr < l)
		return 0;
	int m = l + r >> 1;
	return query_x(xl, xr, yl, yr, l, m, xid<<1) +
		query_x(xl, xr, yl, yr, m+1, r, xid<<1|1);
}

int main()
{
	for(int op; ~scanf("%d", &op); )
	{
		if(op == 0)
		{
			scanf("%d", &n);
			memset(tree, 0, sizeof tree);
		}
		else if(op == 1)
		{
			int x, y, a;
			scanf("%d%d%d", &x, &y, &a);
			update_x(x, y, a, 0, n-1, 1);
		}
		else if(op == 2)
		{
			int l, b, r, t;
			scanf("%d%d%d%d", &l, &b, &r, &t);
			printf("%d\n", query_x(l, r, b, t, 0, n-1, 1));
		}
		else
			break;
	}
	return 0;
}