HDU-3584-Cube

66 阅读 0 评论 44 点赞

我是靠谱客的博主长情季节，最近开发中收集的这篇文章主要介绍HDU-3584-Cube，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：对于改变A[x1,y1,z1]-A[x2,y2,z2]的值，使0变1，1变0，这个这样都加1，然后查询时 %2即可，关键是如何改变其值，可利用三维树状数组，但要改变的是整个区域的值该如何，例如一维树状数组C[n], 改变A[i]-A[j]的值可以先 Update(i,1)，在Update(j+1,-1),这样Query(i->j)的值都加了1，而Query(j+1-->n)的值就不会改变，而对于三维树状数组也是同样处理

Code :

#include<iostream>
#include<cstring>
using namespace std;

const int MAX_N=105;
int n,m;
int C[MAX_N][MAX_N][MAX_N];

int Lowbit(int x);
void Update(int x,int y,int z,int p);
int Query(int x,int y,int z);
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		memset(C,0,sizeof(C));
		int t,x1,x2,y1,y2,z1,z2;
		while(m--){
			cin>>t>>x1>>y1>>z1;
			if(t){
				cin>>x2>>y2>>z2;
				++x2;	++y2;	++z2;
				Update(x2,y2,z2,1);
				Update(x2,y2,z1,1);
				Update(x2,y1,z2,1);
				Update(x1,y2,z2,1);
				Update(x1,y1,z2,1);
				Update(x1,y2,z1,1);
				Update(x2,y1,z1,1);
				Update(x1,y1,z1,1);
			}else	cout<<(Query(x1,y1,z1)%2)<<endl;
		}
	}
	
	return 0;
}

int Lowbit(int x)
{
	return x&(-x);
}

void Update(int x,int y,int z,int p)
{
	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]+=p;
}

int Query(int x,int y,int z)
{
	int ans=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))
				ans+=C[i][j][k];
	return ans;
}