题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3584
分析:题意很简单,就是一个在三维上变化的,输入区间时把这个区间的上的1变为0,0变为1,输入查询时,求出即可。
刚开始想到是线段树,可是三维无从下手,网上查了一些答案,使用的都是树状数组,更新时要注意容斥原理,每个维度的组合2^3=8.
求取结果使用的是 sum(x1,y1,z1)&1 或是 sum(x1,y1,z1)%2,这点还不是很清楚。。。有待在理解理解╮(╯▽╰)╭
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define MAXN 105 using namespace std; int cube[MAXN][MAXN][MAXN]; int N,M; int low_bit(int x) { return x & (-x); } //更新三维树状数组 void update(int x,int y,int z) { for(int i = x; i <= N; i += low_bit(i)) for(int j = y; j <= N; j += low_bit(j)) for(int k = z; k <= N; k += low_bit(k)) cube[i][j][k]++; } int sum(int x,int y,int z) { int ans=0; for(int i = x; i > 0; i -= low_bit(i)) for(int j = y; j > 0; j -= low_bit(j)) for(int k = z; k > 0; k -= low_bit(k)) ans += cube[i][j][k]; return ans; } int main() { int oper; int x1,y1,z1,x2,y2,z2; while(scanf("%d%d",&N,&M)!=EOF) { memset(cube,0,sizeof(cube)); for(int i = 0; i < M; i++) { scanf("%d",&oper); if(oper==1) { scanf("%d%d%d %d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); //三维树状数组更新,容斥原理 update(x1,y1,z1); update(x1,y1,z2+1); update(x1,y2+1,z1); update(x1,y2+1,z2+1); update(x2+1,y1,z1); update(x2+1,y1,z2+1); update(x2+1,y2+1,z1); update(x2+1,y2+1,z2+1); } else if(oper == 0) { scanf("%d%d%d",&x1,&y1,&z1); printf("%d\n",sum(x1,y1,z1)&1); } } } return 0; }
本文转自NewPanderKing51CTO博客,原文链接: http://www.cnblogs.com/newpanderking/archive/2012/11/29/2794959.html,如需转载请自行联系原作者