HDOJ 3584

发表于 |

题目

Given an $N\times N\times 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].

数据范围

$1\leq N \leq 100 \quad \sum M \leq 10^4$

做法

三维的“区间修改，点单查询”，可以用树状数组的“单点修改，区间查询”做。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 105;
int N, M;
struct BIT
{
	int dat[MAX_N][MAX_N][MAX_N], n;
	void init(int n_) {
		memset(dat, 0, sizeof dat);
		n = n_;
	}
    inline int lowbit(int i) {return i & -i;}
  
	void add(int x, int y, int z, int v)
	{
		for (int i = x; i <= n; i += lowbit(i)) {
			for (int j = y; j <= n; j += lowbit(j)) {
				for (int k = z; k <= n; k += lowbit(k)) {
					dat[i][j][k] += v;
				}
			}
		}
	}
	int sum(int x, int y, int z)
	{
		int s = 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)) {
					s += dat[i][j][k];
				}
			}
		}
		return s & 1;
	}
} bit;
int main()
{
	while (scanf("%d%d", &N, &M) != EOF) {
		bit.init(N);
		while (M--) {
			int op, x[2], y[2], z[2];
			scanf("%d", &op);
			if (op) {
				scanf("%d%d%d%d%d%d", &x[0], &y[0], &z[0], &x[1], &y[1], &z[1]);
				bit.add(x[0], y[0], z[0], 1);
				bit.add(x[1] + 1, y[0], z[0], 1);
				bit.add(x[0], y[1] + 1, z[0], 1);
				bit.add(x[1] + 1, y[1] + 1, z[0], 1);
				bit.add(x[0], y[0], z[1] + 1, 1);
				bit.add(x[1] + 1, y[0], z[1] + 1, 1);
				bit.add(x[0], y[1] + 1, z[1] + 1, 1);
				bit.add(x[1] + 1, y[1] + 1, z[1] + 1, 1);
			}
			else {
				scanf("%d%d%d", &x[0], &y[0], &z[0]);
				printf("%d\n", bit.sum(x[0], y[0], z[0]));
			}
		}
	}
	return 0;
}