HDU 3584 Cube --三维树状数组

题意:给一个三维数组n*n*n,初始都为0,每次有两个操作:

1. 翻转(x1,y1,z1) -> (x2,y2,z2)

0. 查询A[x][y][z] (A为该数组)

解法:树状数组维护操作次数,一个数被操作偶数次则相当于没被操作。

每次更新时在8个位置更新:

HDU 3584 Cube --三维树状数组。相当于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[][][];
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 = ;
for(int i=x;i>;i-=lowbit(i))
for(int j=y;j>;j-=lowbit(j))
for(int k=z;k>;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,,sizeof(c));
while(q--)
{
scanf("%d",&op);
if(op == )
{
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
modify(x1,y1,z1,);
modify(x1,y1,z2+,-);
modify(x1,y2+,z1,-);
modify(x1,y2+,z2+,);
modify(x2+,y1,z1,-);
modify(x2+,y1,z2+,);
modify(x2+,y2+,z1,);
modify(x2+,y2+,z2+,-);
}
else
{
scanf("%d%d%d",&x,&y,&z);
int sum = getsum(x,y,z);
printf("%d\n",sum%);
}
}
}
return ;
}
上一篇:mybatis源码学习(一) 原生mybatis源码学习


下一篇:javascript——迭代方法