Cube

Cube

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 2614    Accepted Submission(s): 1314

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

 题意:

１.把空间上以(x1，y1,z1),(x2,y2,z2)为端点的区域所有的1变成0，0变成1.

2.求出(1,1,1)->(x,y,z)的区域的值.

转化一下思想,成为前缀和,然后&1,就知道当前位置是1还是0了.

详见代码.

#include <iostream>
#include <cstring>
#define N 105
using namespace std;

int sum[N][N][N];

int lowbit(int x){ return x&(-x); }

void update(int a,int b,int c){
    for(int i = a;i<=N;i+=lowbit(i)){
        for(int j = b;j<=N;j+=lowbit(j)){
            for(int k = c; k<=N; k += lowbit(k)){
                sum[i][j][k]++;
            }
        }
    }
}

int query(int a,int b,int c){
    int ans = 0;
    for(int i = a;i>0;i-=lowbit(i)){
        for(int j = b;j>0;j-=lowbit(j)){
            for(int k = c;k>0;k-=lowbit(k)){
                ans += sum[i][j][k];
            }
        }
    }
    return ans;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        memset(sum,0,sizeof(sum));
        int p,x,y,z,x1,y1,z1;
        while(m--){
            cin>>p;
            if(p){
                cin>>x>>y>>z>>x1>>y1>>z1;
                update(x,y,z);
                update(x,y,z1+1);
                update(x,y1+1,z);
                update(x1+1,y,z);
                update(x1+1,y1+1,z);
                update(x1+1,y,z1+1);
                update(x,y1+1,z1+1);
                update(x1+1,y1+1,z1+1);
            }else{
                cin>>x>>y>>z;
                cout<<(query(x,y,z)&1)<<endl;
            }
        }
    }
    return 0;
}