HDU3584(树状数组)

92 阅读 0 评论 61 点赞

我是靠谱客的博主潇洒舞蹈，最近开发中收集的这篇文章主要介绍HDU3584(树状数组)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：给一个N阶立方体，初始值为0,。有两种操作：1、对所给长方体内所有的值取非；0、查询该点的值。

思路：三维树状数组，更新长方体的8个顶点。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
int n, m;
int a[111][111][111];
int lowbit(int x)
{
    return x & (-x);
}
void modify(int x, int y, int z)
{
    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))
            {
                a[i][j][k] ^= 1;
            }
        }
    }
}
int query(int x, int y, int z)
{
    int res = 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))
            {
                res += a[i][j][k];
            }
        }
    }
    return res;
}
int main()
{
    int x1, y1, z1, x2, y2, z2, x, y, z;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(a, 0, sizeof a);
        while(m--)
        {
            int op;
            scanf("%d", &op);
            if(op == 1)
            {
                scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
                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);
                if(query(x, y, z) % 2)
                {
                    printf("1n");
                }
                else
                {
                    printf("0n");
                }
            }
        }
    }
    return 0;
}