首页 > 代码库 > HDU 3584 Cube --三维树状数组
HDU 3584 Cube --三维树状数组
题意：给一个三维数组n*n*n，初始都为0，每次有两个操作：
1. 翻转(x1,y1,z1) -> (x2,y2,z2)
0. 查询A[x][y][z] （A为该数组）
解法：树状数组维护操作次数，一个数被操作偶数次则相当于没被操作。
每次更新时在8个位置更新：
。相当于8个二进制数：000,001,010,011,100,101,110,111. （我是由二维推过来的）
其实不用有的为-1，直接1也行，因为反正会改变奇偶性。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;int c[105][105][105];int n;int lowbit(int x) { return x & (-x); }void modify(int x,int y,int z,int val){ 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)) c[i][j][k] += val;}int getsum(int x,int y,int z){ int sum = 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)) sum += c[i][j][k]; return sum;}int main(){ int q,op; int x,y,z,x1,y1,z1,x2,y2,z2; while(scanf("%d%d",&n,&q)!=EOF) { memset(c,0,sizeof(c)); while(q--) { scanf("%d",&op); if(op == 1) { scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); modify(x1,y1,z1,1); modify(x1,y1,z2+1,-1); modify(x1,y2+1,z1,-1); modify(x1,y2+1,z2+1,1); modify(x2+1,y1,z1,-1); modify(x2+1,y1,z2+1,1); modify(x2+1,y2+1,z1,1); modify(x2+1,y2+1,z2+1,-1); } else { scanf("%d%d%d",&x,&y,&z); int sum = getsum(x,y,z); printf("%d\n",sum%2); } } } return 0;}
HDU 3584 Cube --三维树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。