Cube

Problem Description

Given an N*N*N 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
题意:在一个三维长方体里把0元素改成1或者把1改成0或者询问某个位置是0还是1.
分析:
    非树状数组莫属,其他数据结构都太帅了,用不着。
    先说说一维上的树状数组,什么问题都得成最简单的开始,理解后才能推广到多维或复杂的。
    把对某个方体的修改操作看做是对某个方体的操作数+1,那一个位置操作数的奇偶性决定了它的值。
树状数组1位置是管1的,2位置是管1到2的,3是管3的,4是管1到4的......所以对一个区间操作,这个区间首先按树状数组的分区规则,会被分成若干个不相交的区间,在树状数组里对应的就是若干不相交的小树。
    比如对1到3操作,会分成分别对[1,2],[3,3]两段的操作;对2到4的操作,可以分成[2,2],[3,3],[4,4],但是对这种情况,按这种方式去修改树状数组是麻烦的,可以转化成分别对[1,4]操作,再对[1,1]操作,这样[1,1]被修改了两次,所以相当于没修改过(配合这题的奇偶性),也可处理成对[1,4]的操作数+1,再对[1,1]的操作数-1。
    知道每段的信息保存操作次数,可以通过叠加就知道每个位置的操作数。
比如对1到3操作了一次,c[2] = 1(对应[1,2]的区间),c[3] = 1(对应[3,3]区间);再对1操作,则c[1] = 1(对应[1,1]区间)。则1的操作数是c[1] + c[2]。
    到此还不理解的,建议最好看看树状数组的详细结构,然后画一画就应该清楚多了,表达上的不便请原谅,这个算是比较水的,不过对树状数组的理解是有点用处的,还有就是在树状数组上对方块的切割,例如对对2到4的操作需要处理成[1,4]操作,再对[1,1]操作 ,将这个操作推广到3维。
    一维的是区间管区间,二维是方块管理方块,三维是方体管理方体,本质跟一维一样。
#include <stdio.h>
#include 
<stdlib.h>
#include 
<iostream>
#define maxn 110
using namespace std;
int c[maxn][maxn][maxn];
int n;
void set()
{
    
int i, j, k;
    
for (i = 0; i <= n; i++)
    {
        
for (j = 0; j <= n; j++)
        {
            
for (k = 0; k <= n; k++)
            {
                c[i][j][k] 
= 0;
            }
        }
    }
}
inline 
int lowbit(int x)
{
    
return x & (-x);
}
void update(int x, int y, int z)//分块更新或操作 
{
    
int i, j, k;
    
for (i = x; i > 0; i -= lowbit(i))
    {
        
for (j = y; j > 0; j -= lowbit(j))
        {
            
for (k = z; k > 0; k -= lowbit(k))
            {
                c[i][j][k]
++;
            }
        }
    }
}
int sum(int x, int y, int z)//向上叠加每个父节点的操作次数 
{
    
int i, j, k, var = 0;
    
for (i = x; i <= n; i += lowbit(i))
    {
        
for (j = y; j <= n; j += lowbit(j))
        {
            
for (k = z; k <= n; k += lowbit(k))
            {
                var 
+= c[i][j][k];
            }
        }
    }
    
return var;
}
int main()
{
    
int m, op, x1, y1, z1, x2, y2, z2, ans;
    
while (scanf("%d%d"&n, &m) - EOF)
    {
        
set();
        
while (m--)
        {
            scanf(
"%d%d%d%d"&op, &x1, &y1, &z1);
            
if (op == 1)
            {
                scanf(
"%d%d%d"&x2, &y2, &z2);
                update(x2, y2, z2);
                update(x2, y1 
- 1, z2);
                update(x1 
- 1, y2, z2);
                update(x1 
- 1, y1 - 1, z2);
                
//--------
                update(x2, y2, z1 - 1);
                update(x2, y1 
- 1, z1 - 1);
                update(x1 
- 1, y2, z1 - 1);
                update(x1 
- 1, y1 - 1, z1 - 1);
            }
            
else
            {
                ans 
= sum(x1, y1, z1);
                printf(
"%d\n", ans % 2);
            }
        }
    }
    
return 0;
}
/*
2 100
1 2 2 2 2 2 2
0 1 1 1


1
2 10
1 2 1 2 2
Q 2 2
1 2 1 2 1
Q 1 1
1 1 1 2 1
1 1 2 1 2
1 1 1 2 2
Q 1 1
1 1 1 2 1
Q 2 1
*/