【题解】HDU3584 Cube

传送门

题目大意：你有两种操作

• $1 x1 y1 z1 x2 y2 z2$，将 $(x1, y1, z1)$ 到 $(x2, y2, z2)$ 中所有数字取反。
• $2 x1 y1 z1$ 查询 $(x1, y1, z1)$ 位置上的值。

一看就知道要用到拓展到三维的树状数组。树状数组拓展到高维的情况我在这里已经讲过了，所以不再讲。
首先可以看到题目要求的是取反操作，但直接来讲不便维护。所以我们考虑每次操作都是+1，再最后查询的时候将答案&1（取出最末尾，实际上就是奇数则1偶数则0，符合异或操作的自反性）就可以了。
3D树状数组模板

int c[MAXSIZE][MAXSIZE][MAXSIZE];
namespace BIT_3D{
    inline int lowbit(int x) {
        return x & (-x);
    }
    void update(int x, int y, int z, int w) {
        for (int i = x; i <= MAXSIZE; i += lowbit(i)) 
            for (int j = y; j <= MAXSIZE; j += lowbit(j))
                for (int k = z; k <= MAXSIZE; k += lowbit(k)) 
                    c[i][j][k] += w;
    }
    int query(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 += c[i][j][k];
        return ret;
    }
}
using namespace BIT_3D;

之前我们考虑过单点修改区间查询，现在我们要面临的是区间修改和单店查询，这就要用到差分的技巧。
一维的差分：给 $[a, b]$ 整体加1相当于在 $a$ 的位置加上1， 在 $b-1$ 的位置减去1，最后1到n求和之后就是答案。画个表格理性分析一下：
简单起见，原来的数组元素全部置0，要在 $[1, 6]$ $[4, 7]$ $[2, 3]$ $[8, 9]$上加上1

忧伤可以看出差分的高效性。
差分拓展到高维其实很方便，根据容斥原理进行拓展到高维。
而我们的插入和查询操作并不是有先后的，而是穿插进行的。所以不便直接累加，只要每次查询的时候进行 $query()$ 即可。想想就是原来的 $query()$ 求出的是从 $(x, y, z)$ 到 $(1, 1, 1)$ 的全部和。而有了差分操作，这个全部和直接代表了原来这个位置所应有的值。就像一维差分一样，假设我们要求 $a[7]$ 的值，只需要计算 $sum_{i = 1}^7 sum[i]$ 即可。
最后说一声，这道题的差分部分极考眼力，如果WA了多半是差分哪个地方写错了当然我不会说我把memset放在了namespace里面然后就莫名奇妙的WA了n次。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXSIZE 105
int c[MAXSIZE][MAXSIZE][MAXSIZE];
namespace BIT_3D{
    inline int lowbit(int x) {
        return x & (-x);
    }
    void update(int x, int y, int z, int w) {
        for (int i = x; i <= MAXSIZE; i += lowbit(i)) 
            for (int j = y; j <= MAXSIZE; j += lowbit(j))
                for (int k = z; k <= MAXSIZE; k += lowbit(k)) 
                    c[i][j][k] += w;
    }
    int query(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 += c[i][j][k];
        return ret;
    }
}
using namespace BIT_3D;
int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        memset(c, 0, sizeof c);
        while (m--) {
            int opt, x1, y1, z1, x2, y2, z2;
            scanf("%d", &opt);
            if (opt == 1) {
                scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
                update(x1, y1, z1, 1);
                update(x2 + 1, y1, z1, 1);
                update(x1, y2 + 1, z1, 1);
                update(x1, y1, z2 + 1, 1);
                update(x2 + 1, y2 + 1, z1, 1);
                update(x2 + 1, y1, z2 + 1, 1);
                update(x1, y2 + 1, z2 + 1, 1);
                update(x2 + 1, y2 + 1, z2 + 1, 1);
            }
            else {
                scanf("%d%d%d", &x1, &y1, &z1);
                printf("%dn", query(x1, y1, z1) & 1);
            }
        }
    }
    return 0;
}

最后

以上就是幽默招牌为你收集整理的【题解】HDU3584 Cube的全部内容，希望文章能够帮你解决【题解】HDU3584 Cube所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。