hdu 4456 Crowd(二维树状数组)

本文主要是介绍hdu 4456 Crowd(二维树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4456 Crowd

题目大意：给定N，然后M次操作

1 x y z：在x，y的位置加z
2 x y z：询问与x，y曼哈顿距离小于z的点值和。

解题思路：将矩阵旋转45度，然后询问就等于是询问一个矩形，可以用容斥定理搞，维护用二维树状数组，但是空间开

不下，直接用离散化，将有用到的点处理出来。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 4000005;
const int maxm = 80005;#define lowbit(x) ((x)&(-x))
int N, M, W, E, H[maxn+5], fenw[maxn + 5];
int O[maxm], X[maxm], Y[maxm], Z[maxm];inline int find (int x) {return lower_bound(H + 1, H + E, x) - H;
}void hashPoint (int x, int y) {for (int i = x; i <= W; i += lowbit(i)) {for (int j = y; j <= W; j += lowbit(j))H[E++] = i * W + j;}
}void add(int x, int y, int d) {for (int i = x; i <= W; i += lowbit(i)) {for (int j = y; j <= W; j += lowbit(j)) {int pos = find(i * W + j);fenw[pos] += d;}}
}int sum (int x, int y) {int ret = 0;for (int i = x; i; i -= lowbit(i)) {for (int j = y; j; j -= lowbit(j)) {int pos = find(i * W + j);if (H[pos] == i * W + j)ret += fenw[pos];}}return ret;
}void init () {E = 1;W = 2 * N;scanf("%d", &M);memset(fenw, 0, sizeof(fenw));for (int i = 1; i <= M; i++) {scanf("%d%d%d%d", &O[i], &X[i], &Y[i], &Z[i]);int x = X[i] - Y[i] + N;int y = X[i] + Y[i];if (O[i] == 1)hashPoint(x, y);}sort(H + 1, H + E);E = unique(H + 1, H + E) - H;
}void solve() {for (int i = 1; i <= M; i++) {int x = X[i] - Y[i] + N;int y = X[i] + Y[i];if (O[i] == 1)add(x, y, Z[i]);else {int a = max(1, x - Z[i]);int b = max(1, y - Z[i]);int c = min(W, x + Z[i]);int d = min(W, y + Z[i]);printf("%d\n", sum(c, d) - sum(c, b-1) - sum(a-1, d) + sum(a-1, b-1));}}
}int main () {while (scanf("%d", &N) == 1 && N) {init();solve();}return 0;
}