[题解]hdu Cube

63 阅读 0 评论 42 点赞

我是靠谱客的博主动听海燕，最近开发中收集的这篇文章主要介绍[题解]hdu Cube，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Cube

Problem Description
Given an NNN cube A, whose elements are either 0 or 1. A[i, j, k] means the number in the i-th row , j-th column and k-th layer. Initially we have A[i, j, k] = 0 (1 <= i, j, k <= N).
We define two operations, 1: “Not” operation that we change the A[i, j, k]=!A[i, j, k]. that means we change A[i, j, k] from 0->1,or 1->0. (x1<=i<=x2,y1<=j<=y2,z1<=k<=z2).
0: “Query” operation we want to get the value of A[i, j, k].
Input
Multi-cases.
First line contains N and M, M lines follow indicating the operation below.
Each operation contains an X, the type of operation. 1: “Not” operation and 0: “Query” operation.
If X is 1, following x1, y1, z1, x2, y2, z2.
If X is 0, following x, y, z.
Output
For each query output A[x, y, z] in one line. (1<=n<=100 sum of m <=10000)
Sample Input
2 5
1 1 1 1 1 1 1
0 1 1 1
1 1 1 1 2 2 2
0 1 1 1
0 2 2 2
Sample Output
1
0
1
Author
alpc32
Source
2010 ACM-ICPC Multi-University Training Contest（15）——Host by NUDT

谷歌翻译~~

问题描述
给定N * N * N立方体A，其元素为0或1. A [i，j，k]表示第i行，第j列和第k层中的数字。最初我们有A [i，j，k] = 0（1 <= i，j，k <= N）。
我们定义了两个操作，1：“不”操作，我们改变A [i，j，k] =！A [i，j，k]。这意味着我们将A [i，j，k]从0-> 1或1-> 0改变。（X1 <= I <= X2，Y1 <= j的<= Y2，Z1 <= K <= Z2）。
0：“查询”操作我们想得到A [i，j，k]的值。
输入
多例。
第一行包含N和M，M行跟随指示下面的操作。
每个操作都包含一个X，即操作类型。1：“不”操作和0：“查询”操作。
如果X是1，则跟随x1，y1，z1，x2，y2，z2。
如果X为0，则遵循x，y，z。
产量
对于每行查询输出A [x，y，z]。（1 <= n <= 100总和m <= 10000）
样本输入
2 5
1 1 1 1 1 1 1
0 1 1 1
1 1 1 1 2 2 2
0 1 1 1
0 2 2 2
样本输出
1
0
1

solution

考虑异或
一段区间翻转01，相当于异或上1
把模型转换成前缀异或“和”即可

难点是修改
由二维推广到三维，具体见代码

Code：

#include <bits/stdc++.h>
#define maxn 110
using namespace std;
int n, m, tree[maxn][maxn][maxn];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

void add(int x, int y, int z){ int Y = y, Z = z; for (; x <= maxn; x += (x & -x)) for (y = Y; y <= maxn; y += (y & -y)) for (z = Z; z <= maxn; z += (z & -z)) tree[x][y][z] ^= 1; }
int query(int x, int y, int z){ int Y = y, Z = z, sum = 0; for (; x; x -= (x & -x)) for (y = Y; y; y -= (y & -y)) for (z = Z; z; z -= (z & -z)) sum ^= tree[x][y][z]; return sum; }
//三维树状数组，超级压行

int main(){
    while (scanf("%d%d", &n, &m) == 2){
        memset(tree, 0, sizeof(tree));
        while (m--){
            int opt = read();
            if (opt == 0){
                int x = read(), y = read(), z = read();
                printf("%dn", query(x, y, z));
            } else{
                int x1 = read(), y1 = read(), z1 = read(), x2 = read(), y2 = read(), z2 = read();
                add(x1, y1, z1);
                add(x2 + 1, y1, z1); add(x1, y2 + 1, z1); add(x1, y1, z2 + 1);
                add(x2 + 1, y2 + 1, z1); add(x2 + 1, y1, z2 + 1); add(x1, y2 + 1, z2 + 1);
                add(x2 + 1, y2 + 1, z2 + 1);
                //非常有层次感的三维更新（其实我就是从二维里找规律出来的）
            }
        }
        
    }
    return 0;
}