首页 > 代码库 > 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;
}
hdu 4456 Crowd(二维树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。