从多校联合 NUDT 第二题 Cube 想到的关于树状数组的结论

发表于 分类于

这题一眼看去就是更新区间查找点，典型的树状数组解法，但是如果用三维树状数组的话，会遇到一个难题，那就是怎么分割？

我们看简单的问题开始，对于一维的情况，将区间 (a,b)(a,b) 进行更新，那么就在 aa 处加 vv，b+1b+1 处减 vv 即可。

对于二维的情况，那就麻烦一点，将区域 (x1,y1)(x_1, y_1) 到 (x2,y2)(x_2, y_2) 进行更新，那么就在 (x1,y1)(x_1, y_1) 处加 vv，在 (x2+1,y1)(x_2+1,y_1) 和 (x1,y2+1)(x_1,y_2+1) 处减 v，在 (x2+1,y2+1)(x_2+1, y_2+1) 处加 v 即可。

那么三维的呢？经过画图，我得到了结论，那就是 (x1,y1,z1)(x_1, y_1, z_1) 加 v，和 (x1,y1,z1)(x_1, y_1, z_1) 相邻奇数长度的点减 vv，这些点有 (x2+1,y1,z1)(x_2+1, y_1, z_1)、(x1,y2+1,z1)(x_1, y_2+1, z_1)、(x1,y1,z2+1)(x_1, y_1, z_2+1) 还有 (x2+1,y2+1,z2+1)(x_2+1, y_2+1, z_2+1)，剩下的就是加 vv 了。

把三个维度不同的树状数组的情况和在一起，源点 PP 加 vv 和 PP 相邻奇数位置的减 vv，偶数位置的加 vv，这样就可以快速地记下来全部的切割情况了。

我的代码：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

const int MAX = 110;

int n;
int tree[MAX][MAX][MAX];

void add(int x, int y, int z, int v) {
  int tmp1 = y;
  int tmp2 = z;
  while (x <= n) {
    y = tmp1;
    while (y <= n) {
      z = tmp2;
      while (z <= n) {
        tree[x][y][z] += v;
        z += z & -z;
      }
      y += y & -y;
    }
    x += x & -x;
  }
}

int read(int x, int y, int z) {
  int tmp1 = y;
  int tmp2 = z;
  int sum = 0;
  while (x) {
    y = tmp1;
    while (y) {
      z = tmp2;
      while (z) {
        sum += tree[x][y][z];
        z -= z & -z;
      }
      y -= y & -y;
    }
    x -= x & -x;
  }
  return sum;
}

int main() {
  int m;
  int x1, x2, y1, y2, z1, z2, op;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++) tree[i][j][k] = 0;
    for (int i = 0; i < m; i++) {
      scanf("%d", &op);
      if (op) {
        scanf("%d%d%d", &x1, &y1, &z1);
        scanf("%d%d%d", &x2, &y2, &z2);
        add(x1, y1, z1, 1);
        add(x2 + 1, y1, z1, -1);
        add(x1, y2 + 1, z1, -1);
        add(x1, y1, z2 + 1, -1);
        add(x2 + 1, y2 + 1, z1, 1);
        add(x2 + 1, y1, z2 + 1, 1);
        add(x1, y2 + 1, z2 + 1, 1);
        add(x2 + 1, y2 + 1, z2 + 1, -1);
      } else {
        scanf("%d%d%d", &x1, &y1, &z1);
        printf("%d\n", read(x1, y1, z1) % 2);
      }
    }
  }
  return 0;
}

总结：每次做题后要反思，不能做一题过一题，宁可花时间想怎么优化代码，毕竟这个对自己好处更大。做题不贵多，而贵精。