hdu 3584 Cube 三维树状数组

这个题意思是翻转一个01立方体。翻转多次后再查询某个点的值。
还是利用上一篇文章的思想,把翻转操作转换为单点更新操作。把查询操作转换为利用树状数组查询和的方式。这样每次操作的复杂度都是logN的3次。而直接翻转立方体的复杂度是N的3次。
这个题最麻烦的地方是空间想象能力。因为要翻转8个点才能完成一次立方体翻转。比如,翻转(x,y,z)相当于以该点作为左上角做一个无限立方体,把该立方体翻转。这样就会翻转多余的部分,那么需要把多翻转的部分翻转回来。最后的思考结果发现,只要对每个顶点翻转一次即可。至于为什么这样,自己去计算重复翻转的部分就会明白了。刚好确实是把每个点翻转了一次。

代码如下:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
int nSum[MAX_N + 10][MAX_N + 10][MAX_N + 10];
int nN, nM;

int LowBit(int nPos)
{
return nPos & (-nPos);
}

void Add(int nX, int nY, int nZ)
{
for (int i = nX; i <= nN; i += LowBit(i))
{
for (int j = nY; j <= nN; j += LowBit(j))
{
for (int k = nZ; k <= nN; k += LowBit(k))
{
nSum[i][j][k]++;
}
}
}
}

int Query(int nX, int nY, int nZ)
{
int nAns = 0;

for (int i = nX; i > 0; i -= LowBit(i))
{
for (int j = nY; j > 0; j -= LowBit(j))
{
for (int k = nZ; k > 0; k -= LowBit(k))
{
nAns += nSum[i][j][k];
}
}
}
return nAns;
}

int main()
{
int nCmd;
int nX, nY, nZ;
int nX1, nY1, nZ1;
int nX2, nY2, nZ2;

while (scanf("%d%d", &nN, &nM) == 2)
{
memset(nSum, 0, sizeof(nSum));
while (nM--)
{
scanf("%d", &nCmd);
if (nCmd == 0)
{
scanf("%d%d%d", &nX, &nY, &nZ);
printf("%d\n", Query(nX, nY, nZ) % 2);
}
else
{
scanf("%d%d%d%d%d%d", &nX1, &nY1, &nZ1, &nX2, &nY2, &nZ2);
if (nX1 > nX2)swap(nX1, nX2);
if (nY1 > nY2)swap(nY1, nY2);
if (nZ1 > nZ2)swap(nZ1, nZ2);
Add(nX1, nY1, nZ1);

Add(nX2 + 1, nY1, nZ1);
Add(nX1, nY2 + 1, nZ1);
Add(nX1, nY1, nZ2 + 1);

Add(nX1, nY2 + 1, nZ2 + 1);
Add(nX2 + 1, nY1, nZ2 + 1);
Add(nX2 + 1, nY2 + 1, nZ1);

Add(nX2 + 1, nY2 + 1, nZ2 + 1);
}
}
}

return 0;
}