Cube
Problem Description
Given an N*N*N cube A, whose elements are either 0 or 1. A[i, j, k] means the number in the i-th row , j-th column and k-th layer. Initially we have A[i, j, k] = 0 (1 <= i, j, k <= N).
We define two operations, 1: “Not” operation that we change the A[i, j, k]=!A[i, j, k]. that means we change A[i, j, k] from 0->1,or 1->0. (x1<=i<=x2,y1<=j<=y2,z1<=k<=z2).
0: “Query” operation we want to get the value of A[i, j, k].
Input
Multi-cases.
First line contains N and M, M lines follow indicating the operation below.
Each operation contains an X, the type of operation. 1: “Not” operation and 0: “Query” operation.
If X is 1, following x1, y1, z1, x2, y2, z2.
If X is 0, following x, y, z.
Output
For each query output A[x, y, z] in one line. (1<=n<=100 sum of m <=10000)
Sample Input
2 5
1 1 1 1 1 1 1
0 1 1 1
1 1 1 1 2 2 2
0 1 1 1
0 2 2 2
Sample Output
1
0
1
/*AC代码*/
#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; const int N=; int n,m,arr[N][N][N]; int lowbit(int x)
{
return x&(-x);
} void update(int i,int j,int k,int val)
{
while(i<=n)
{
int tmpj=j;
while(tmpj<=n)
{
int tmpk=k;
while(tmpk<=n)
{
arr[i][tmpj][tmpk]+=val;
tmpk+=lowbit(tmpk);
}
tmpj+=lowbit(tmpj);
}
i+=lowbit(i);
}
} int Sum(int i,int j,int k)
{
int ans=;
while(i>)
{
int tmpj=j;
while(tmpj>)
{
int tmpk=k;
while(tmpk>)
{
ans+=arr[i][tmpj][tmpk];
tmpk-=lowbit(tmpk);
}
tmpj-=lowbit(tmpj);
}
i-=lowbit(i);
}
return ans;
} int main()
{ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m))
{
memset(arr,,sizeof(arr));
int x1,y1,z1,x2,y2,z2;
int op;
while(m--)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
update(x2+, y2+, z2+, );
update(x1, y2+, z2+, );
update(x2+, y1, z2+, );
update(x2+, y2+, z1, );
update(x1, y1, z2+, );
update(x2+, y1, z1, );
update(x1, y2+, z1, );
update(x1, y1, z1, );
}
else
{
scanf("%d%d%d",&x1,&y1,&z1);
printf("%d\n",Sum(x1,y1,z1)&);
//该点的值就是sum(x,y)
}
}
}
return ;
}
感觉三维应该和二维差不多 变一下下就好了
但是我就是wa了 囧 照例，下面的代码 请无视
/*wa代码*/
#include<iostream> using namespace std; int N;
int c[][][]; int lowbit( int x )
{
return x & (-x);
} void update( int x, int y, int z, int delta )
{
int i, j , k;
for(i=x; i<=N; i+=lowbit(i))
{
for(j=y; j<=N; j+=lowbit(j))
{
for(k=z ; k<=N; k+=lowbit(j))
c[i][j][k] += delta;
}
}
} int sum( int x, int y , int z )
{
int res = , i, j , k;
for(i=x; i>; i-=lowbit(i))
{
for(j=y; j>; j-=lowbit(j))
{
for(k=z; k>; k-=lowbit(j))
{
res += c[i][j][k];
}
}
}
return res;
} void init ()
{
int i,j,k;
for(i=;i<=N;i++)
for(j=;j<=N;j++)
for(k=;k<=N;k++)
c[i][j][k]=;
} int main()
{
int x1,y1,z1,x2,y2,z2;
int temp,p; while(scanf("%d%d%",&N,&p)!=EOF)
{
init ();
while(p--)
{
scanf("%d",&temp);
if(temp==)
{
// printf("input x1~z2\n"); scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
update(x2+, y2+, z2+, );
update(x1, y2+, z2+, );
update(x2+, y1, z2+, );
update(x2+, y2+, z1, );
update(x1, y1, z2+, );
update(x2+, y1, z1, );
update(x1, y2+, z1, );
update(x1, y1, z1, ); }
else if(temp==)
{
scanf("%d%d%d",&x1,&y1,&z1);
printf("%d\n",sum(x1,y1,z1)&);
}
}
} return ;
}