這個題意思是翻轉(zhuǎn)一個01立方體。翻轉(zhuǎn)多次后再查詢某個點的值。
還是利用上一篇文章的思想，把翻轉(zhuǎn)操作轉(zhuǎn)換為單點更新操作。把查詢操作轉(zhuǎn)換為利用樹狀數(shù)組查詢和的方式。
這樣每次操作的復(fù)雜度都是logN的3次。而直接翻轉(zhuǎn)立方體的復(fù)雜度是N的3次。
這個題最麻煩的地方是空間想象能力。因為要翻轉(zhuǎn)8個點才能完成一次立方體翻轉(zhuǎn)。比如，翻轉(zhuǎn)(x,y,z)相當(dāng)于
以該點作為左上角做一個無限立方體，把該立方體翻轉(zhuǎn)。這樣就會翻轉(zhuǎn)多余的部分，那么需要把多翻轉(zhuǎn)的部分翻轉(zhuǎn)
回來。最后的思考結(jié)果發(fā)現(xiàn)，只要對每個頂點翻轉(zhuǎn)一次即可。至于為什么這樣，自己去計算重復(fù)翻轉(zhuǎn)的部分就會明白
了。剛好確實是把每個點翻轉(zhuǎn)了一次。
代碼如下：
#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;
}