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
三维树状数组。。加一个for循环就ok
#include
#include
#include
//#include
#include
#include
#include
#include
#define lson o<<1, l, m #define rson o<<1|1, m+1, r using namespace std; typedef long long LL; const int mod = 99999997; const int MAX = 1000000000; const int maxn = 1005; int n, q, x1, y1, z1, x2, y2, z2, op; int c[101][101][101]; void add(int x, int y, int z) { for(int i = x; i <= n; i += i&-i) for(int j = y; j <= n; j += j&-j) for(int k = z; k <= n; k += k&-k) c[i][j][k]++; } int query(int x, int y, int z) { int sum = 0; for(int i = x; i > 0; i -= i&-i) for(int j = y; j > 0; j -= j&-j) for(int k = z; k > 0; k -= k&-k) sum += c[i][j][k]; return sum; } int main() { //freopen("in.txt", "r", stdin); while(cin >> n >> q) { memset(c, 0, sizeof(c)); while(q--) { scanf("%d%d%d%d", &op, &x1, &y1, &z1); if(op) { scanf("%d%d%d", &x2, &y2, &z2); x2++, y2++, z2++; add(x1, y1, z1); add(x1, y1, z2); add(x1, y2, z1); add(x2, y1, z1); add(x1, y2, z2); add(x2, y1, z2); add(x2, y2, z1); add(x2, y2, z2); } else printf("%d\n", query(x1, y1, z1) & 1); } } return 0; }
??
|