hdu 3584 Cube (三维树状数组,更新区间,查询单点)
三维树状数组
容斥那里注意一下。
多组数据因为忘记清空c数组而wa了1次,细心!
/*************************************************************************
> File Name: code/hdu/3584.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月07日 星期五 14时01分53秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E2+5;
25int c[N][N][N];
26int n,m;
27int x1,y1,z1,x2,y2,z2;
28int lowbit( int x)
29{
30 return x&(-x);
31}
32void update ( int x,int y,int z,int delta)
33{
34 for ( int i = x; i <= n ; i = i + lowbit(i))
35 {
36 for ( int j = y ; j <= n ; j = j + lowbit(j))
37 {
38 for ( int k = z ; k <= n ; k = k + lowbit(k))
39 {
40 c[i][j][k] += delta;
41 }
42 }
43 }
44}
1int sum (int x,int y,int z)
2{
3 int res = 0;
4 for ( int i = x; i >= 1 ; i -= lowbit(i))
5 {
6 for ( int j = y ; j >= 1 ; j -= lowbit(j))
7 {
8 for ( int k = z ; k >= 1 ; k -= lowbit(k))
9 {
10 res = res + c[i][j][k];
11 }
12 }
13 }
14 return res;
15}
16int main()
17{
18 int op;
19 while (scanf("%d %d",&n,&m)!=EOF)
20 {
21 memset(c,0,sizeof(c));
22 for ( int i = 1 ; i <= m ; i ++ )
23 {
24 scanf("%d",&op);
25 if (op)
26 {
27 scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2);
28 update (x1,y1,z1,1);
29 update (x1,y1,z2+1,1);
30 update (x1,y2+1,z1,1);
31 update (x2+1,y1,z1,1);
1 update (x2+1,y2+1,z1,1);
2 update (x2+1,y1,z2+1,1);
3 update (x1,y2+1,z2+1,1);
4 update (x2+1,y2+1,z2+1,1);
1 }
2 else
3 {
4 scanf("%d %d %d",&x1,&y1,&z1);
5 cout<<sum(x1,y1,z1)%2<<endl;
6 }
7 }
8 }
return 0;
}