hdu 3584 Cube(树状数组)

简介:

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3584

分析:题意很简单,就是一个在三维上变化的,输入区间时把这个区间的上的1变为0,0变为1,输入查询时,求出即可。

刚开始想到是线段树,可是三维无从下手,网上查了一些答案,使用的都是树状数组,更新时要注意容斥原理,每个维度的组合2^3=8.

求取结果使用的是 sum(x1,y1,z1)&1 或是 sum(x1,y1,z1)%2,这点还不是很清楚。。。有待在理解理解╮(╯▽╰)╭

复制代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 105
using namespace std;

int cube[MAXN][MAXN][MAXN];
int N,M;

int low_bit(int x)
{
    return x & (-x);
}
//更新三维树状数组
void update(int x,int y,int z)
{
    for(int i = x; i <= N; i += low_bit(i))
    for(int j = y; j <= N; j += low_bit(j))
    for(int k = z; k <= N; k += low_bit(k))
    cube[i][j][k]++;
}

int sum(int x,int y,int z)
{
    int ans=0;
    for(int i = x; i > 0; i -= low_bit(i))
    for(int j = y; j > 0; j -= low_bit(j))
    for(int k = z; k > 0; k -= low_bit(k))
    ans += cube[i][j][k];
    return ans;
}

int main()
{
    int oper;
    int x1,y1,z1,x2,y2,z2;
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        memset(cube,0,sizeof(cube));
        for(int i = 0; i < M; i++)
        {
            scanf("%d",&oper);
            if(oper==1)
            {
                scanf("%d%d%d %d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
                //三维树状数组更新,容斥原理
                update(x1,y1,z1);
                update(x1,y1,z2+1);
                update(x1,y2+1,z1);
                update(x1,y2+1,z2+1);
                update(x2+1,y1,z1);
                update(x2+1,y1,z2+1);
                update(x2+1,y2+1,z1);
                update(x2+1,y2+1,z2+1);
            }
            else if(oper == 0)
            {
                 scanf("%d%d%d",&x1,&y1,&z1);
                 printf("%d\n",sum(x1,y1,z1)&1);
            }

        }
    }

    return 0;
}
复制代码

 

 

 

 











本文转自NewPanderKing51CTO博客,原文链接: http://www.cnblogs.com/newpanderking/archive/2012/11/29/2794959.html,如需转载请自行联系原作者

相关文章
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
132 0
poj 2352 Stars 树状数组
树状数组,简单题,我刚刚开始学的时候就a了,不多说什么了,直接贴代码。
33 0
|
机器学习/深度学习
HDOJ(HDU) 2083 简易版之最短距离(中位数)
HDOJ(HDU) 2083 简易版之最短距离(中位数)
137 0
|
Java BI 机器学习/深度学习
|
人工智能 BI 存储
|
Java
HDU 2689 Sort it【树状数组】
Sort it Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4672    Accepted Submission(s): 3244 ...
1096 0