首页 > 代码库 > hdu 3584 二进制0,1反转 三维树状数组 及三维树状数组模板

hdu 3584 二进制0,1反转 三维树状数组 及三维树状数组模板

2024-07-17 10:09:52   218人阅读

先贴自己类比二维树状数组写的三维树状数组模板： 开始的时候循环体内j=y,k=z，没写，以为自己思路错了，，，hehe.....

更高维的树状数组以此类比


const int MAXN = 100+10;
int c[MAXN][MAXN][MAXN];int X,Y,Z;
int N;

inline int lowbit(int x){return x&(-x);}
void update(int x, int y, int z, int v)
{
    int i=x,j=y,k=z;
    while(i<=X)
    {
        j=y;
        while(j<=Y)
        {
            k=z;
            while(k<=Z)
            {
                c[i][j][k]+=v;
                k+=lowbit(k);
            }
            j+=lowbit(j);
        }
        i+=lowbit(i);
    }
}
int sum(int x, int y, int z)
{
    int i=x,j=y,k=z,ret=0;
    while(i>0)
    {
        j=y;
        while(j>0)
        {
            k=z;
            while(k>0)
            {
                ret+=c[i][j][k];
                k-=lowbit(k);
            }
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
    return ret;
}

http://acm.hdu.edu.cn/showproblem.php?pid=3584

方法仍然是看论文：《浅谈信息学竞赛中的“0”和“1”——二进制思想在信息学竞赛中的应用》 好神奇

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)

const int MAXN = 100+10;
int c[MAXN][MAXN][MAXN];int X,Y,Z;
int N;

inline int lowbit(int x){return x&(-x);}
void update(int x, int y, int z, int v)
{
    int i=x,j=y,k=z;
    while(i<=X)
    {
        j=y;
        while(j<=Y)
        {
            k=z;
            while(k<=Z)
            {
                c[i][j][k]+=v;
                k+=lowbit(k);
            }
            j+=lowbit(j);
        }
        i+=lowbit(i);
    }
}
int sum(int x, int y, int z)
{
    int i=x,j=y,k=z,ret=0;
    while(i>0)
    {
        j=y;
        while(j>0)
        {
            k=z;
            while(k>0)
            {
                ret+=c[i][j][k];
                k-=lowbit(k);
            }
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
    return ret;
}

int main()
{
    //IN("hdu3584.txt");
    int m;
    int op,x1,y1,z1,x2,y2,z2;
    while(~scanf("%d%d",&N,&m))
    {
        CL(c,0);
        X=Y=Z=N;
        while(m--)
        {
            scanf("%d",&op);
            if(op == 1)
            {
                scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
                update(x1,y1,z1,1);
                update(x1,y1,z2+1,1);
                update(x1,y2+1,z1,1);
                update(x2+1,y1,z1,1);
                update(x2+1,y2+1,z2+1,1);
                update(x2+1,y1,z2+1,1);
                update(x1,y2+1,z2+1,1);
                update(x2+1,y2+1,z1,1);
            }
            else
            {
                scanf("%d%d%d",&x1,&y1,&z1);
                printf("%d\n",sum(x1,y1,z1)%2);
            }
        }
    }
    return 0;
}



联系
我们