hdu3584 树状数组

思路：从一维扩展到三维。可以看看poj2155的解法。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define Maxn 102
#define lowbit(x) (x&(-x))
using namespace std;
int C[Maxn][Maxn][Maxn],n;
int Sum(int i,int j,int k)
{
    int sum=0;
    int y,z;
    y=j,z=k;
    while(i)
    {
        j=y;
        while(j)
        {
            k=z;
            while(k)
            {
                sum+=C[i][j][k];
                k-=lowbit(k);
            }
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
    return sum;
}
void update(int i,int j,int k)
{
    int y,z;
    y=j,z=k;
    while(i<=n)
    {
        j=y;
        while(j<=n)
        {
            k=z;
            while(k<=n)
            {
                C[i][j][k]++;
                k+=lowbit(k);
            }
            j+=lowbit(j);
        }
        i+=lowbit(i);
    }
}
int main()
{
    int x1,x2,y1,y2,z1,z2,m,x;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(C,0,sizeof(C));
        while(m--)
        {
            scanf("%d",&x);
            if(x==0)
            {
                scanf("%d%d%d",&x1,&y1,&z1);
                printf("%d
",Sum(x1,y1,z1)&1);
            }
            if(x==1)
            {
                scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
                update(x1,y1,z1);
                update(x1,y2+1,z1);
                update(x2+1,y2+1,z1);
                update(x2+1,y1,z1);
                update(x1,y1,z2+1);
                update(x1,y2+1,z2+1);
                update(x2+1,y2+1,z2+1);
                update(x2+1,y1,z2+1);
            }
        }
    }
    return 0;
}