MiYu原創(chuàng), 轉帖請注明 : 轉載自 ______________白白の屋
題目描述:
2 5 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 2 2 2 0 1 1 1 0 2 2 2
1 0 1
題目分析 :
更新區(qū)間, 查詢一個點, 三維線段樹 直接無視.........數據不是很強, 所以 直接暴力就可以過, 過完發(fā)現自己的時間 在700MS 左右, 看了下rank,
小A 榜首..... 時間竟然才62MS....果然還是要用三維樹狀數組來加速啊 . 不過一直沒理解 用 樹狀數組 解決這題的思路, 今早上終于明白了.
畫個圖先 :
好了 , 看代碼:
樹狀數組代碼 :
/*
Mail to : miyubai@gamil.com My Blog : www.baiyun.me Link : http://www.cnblogs.com/MiYu || http://m.shnenglu.com/MiYu Author By : MiYu Test : 1 Complier : g++ mingw32-3.4.2 Program : HDU_3584 Doc Name : Cube */ //#pragma warning( disable:4789 ) #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <string> #include <set> #include <map> #include <utility> #include <queue> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> using namespace std; inline bool scan_d(int &num) //整數輸入 { char in;bool IsN=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){ IsN=true;num=0;} else num=in-'0'; while(in=getchar(),in>='0'&&in<='9'){ num*=10,num+=in-'0'; } if(IsN) num=-num; return true; } const int MAXN = 105; int mat[MAXN][MAXN][MAXN]; int low[MAXN]; int i, j, k; void setLow () { for ( i = 1; i <= MAXN; ++ i ) low[i] = i & (- i); } void modify ( int x, int y, int z ) { for ( i = x; i <= MAXN; i += low[i] ) { for ( j = y; j <= MAXN; j += low[j] ) { for ( k = z; k <= MAXN; k += low[k] ) mat[i][j][k] ^= 1; } } } int query ( int x, int y, int z ) { int sum = 0; for ( i = x; i > 0; i ^= low[i] ) { for ( j = y; j > 0; j ^= low[j] ) { for ( k = z; k > 0; k ^= low[k] ) sum += mat[i][j][k]; } } return sum & 1; } int main () { setLow (); int N, M; while ( scan_d ( N ) && scan_d ( M ) ) { memset ( mat, 0, sizeof ( mat ) ); while ( M -- ) { int x1,y1,z1,x2,y2,z2; int s; scan_d ( s ); switch ( s ) { case 1: scan_d ( x1 ); scan_d ( y1 ); scan_d ( z1 ); scan_d ( x2 ); scan_d ( y2 ); scan_d ( z2 ); modify ( x1,y1,z1 ); modify ( x1,y1,z2+1 ); modify ( x2+1,y1,z1 ); modify ( x2+1,y1,z2+1 ); modify ( x1,y2+1,z1 ); modify ( x2+1,y2+1,z1 ); modify ( x2+1,y2+1,z2+1 ); modify ( x1,y2+1,z2+1 ); break; case 0: scan_d ( x1 ); scan_d ( y1 ); scan_d ( z1 ); printf ( "%d\n", query ( x1,y1,z1 ) ); } } } return 0; }
暴力代碼 :
/* Mail to : miyubai@gamil.com My Blog : www.baiyun.me Link : http://www.cnblogs.com/MiYu || http://m.shnenglu.com/MiYu Author By : MiYu Test : 1 Complier : g++ mingw32-3.4.2 Program : Doc Name : */ //#pragma warning( disable:4789 ) #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <string> #include <set> #include <map> #include <utility> #include <queue> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> using namespace std; struct node { int x1, x2, y1, y2, z1, z2; }cube[10010]; int main() { int N, M; int x, y, z; while ( scanf ( "%d%d",&N,&M ) != EOF ) { int cnt = 0; while ( M -- ) { int ask; scanf ( "%d", &ask ); switch ( ask ) { case 1: scanf ( "%d%d%d%d%d%d", &cube[cnt].x1,&cube[cnt].y1, &cube[cnt].z1,&cube[cnt].x2, &cube[cnt].y2,&cube[cnt].z2 ); ++ cnt; break; case 0: scanf ( "%d%d%d", &x, &y, &z); int count = 0; for ( int i = 0; i != cnt; ++ i ) if ( cube[i].x1 <= x && x <= cube[i].x2 && cube[i].y1 <= y && y <= cube[i].y2 && cube[i].z1 <= z && z <= cube[i].z2 ) count ^= 1;; puts ( count ? "1" : "0" ); } } } return 0; }
Powered by: C++博客 Copyright © MiYu