我是靠谱客的博主 俊秀玫瑰,这篇文章主要介绍Ural1470-UFOs,现在分享给大家,希望可以做个参考。

维护一个三维树状数组即可。
唯一的难点在于如何分解立方体从而得到从(x1, y1, z1)到(x2, y2, z2)的元素和。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio> const int maxn = 128 + 5; long long bit[maxn][maxn][maxn]; int n; int lowbit(int x) { return x & -x; } void add(int x, int y, int z, int delta) { for (int i = x; i <= n + 1; i += lowbit(i)) { for (int j = y; j <= n + 1; j += lowbit(j)) { for (int k = z; k <= n + 1; k += lowbit(k)) { bit[i][j][k] += delta; } } } } int sum(int x, int y, int z) { int ret = 0; for (int i = x; i > 0; i -= lowbit(i)) { for (int j = y; j > 0; j -= lowbit(j)) { for (int k = z; k > 0; k -= lowbit(k)) { ret += bit[i][j][k]; } } } return ret; } int main(int argc, char const *argv[]) { int m; scanf("%d", &n); while (scanf("%d", &m) == 1 && m != 3) { if (m == 1) { int x, y, z, k; scanf("%d%d%d%d", &x, &y, &z, &k); x++, y++, z++; add(x, y, z, k); } else { int x1, y1, z1, x2, y2, z2; scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2); x1++, y1++, z1++; x2++, y2++, z2++; int ans = sum(x2, y2, z2) - sum(x2, y1-1, z2) - sum(x1-1, y2, z2) + sum(x1-1, y1-1, z2) - sum(x2, y2, z1-1) + sum(x2, y1-1, z1-1) + sum(x1-1, y2, z1-1) - sum(x1-1, y1-1, z1-1); printf("%dn", ans); } } return 0; }

最后

以上就是俊秀玫瑰最近收集整理的关于Ural1470-UFOs的全部内容,更多相关Ural1470-UFOs内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(64)

评论列表共有 0 条评论

立即
投稿
返回
顶部