hdu 3584 Cube 三维树状数组

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

posted on 2012-09-10 15:43 yx 阅读(1481) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年9月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜