Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 17423 | Accepted: 6530 |
Description
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change
it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2
y2", which has been described above.
Output
There is a blank line between every two continuous test cases.
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
Source
传送门:POJ 2155 Matrix
题目大意:给你一个N*N的矩阵,一开始里面所有的元素值均为0,现在给你m次操作,每次操作是修改或者查询。
当为修改操作时,将矩阵中(x1,y1)到(x2,y2)范围内的元素全部反转(0变1,1变0)。
当为查询操作时,询问点(x,y)在经过之前的操作后的值。
题目分析:该题是线段树的区间修改+单点查询。
由于矩阵是二维的,所以我们用二维线段树即可。
二维线段树就是在一维线段树的基础上,每一个子节点都是一棵线段树(也就是树套树),由此构成。
对于本题,不断的异或就好了。具体看代码。
PS:树状数组很好写并且复杂度超级低
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define clear( A , X ) memset ( A , X , sizeof A ) #define lson l , m , o << 1 #define rson m + 1 , r , o << 1 | 1 #define LxRxLyRy Lx , Rx , Ly , Ry const int maxN = 1005 ; bool sum[ maxN << 2 ][ maxN << 2 ] ; int n; void YUpdate ( int L, int R , int l , int r , int o , int x ) { if ( L <= l && r <= R ) sum[ x ][ o ] ^= 1 ; else { int m = ( l + r ) >> 1 ; if ( L <= m ) YUpdate ( L , R , lson , x ) ; if ( m < R ) YUpdate ( L , R , rson , x ) ; } } void XUpdate ( int Lx , int Rx , int Ly , int Ry , int l , int r , int o ) { if ( Lx <= l && r <= Rx ) { YUpdate ( Ly , Ry , 1 , n , 1 , o ) ; } else { int m = ( l + r ) >> 1 ; if ( Lx <= m ) XUpdate ( LxRxLyRy , lson ) ; if ( m < Rx ) XUpdate ( LxRxLyRy , rson ) ; } } bool YQuery ( int Y , int l , int r , int o , int x ) { bool ans = 0 ; ans ^= sum[ x ][ o ] ; if ( l == r ) return ans; int m = ( l + r ) >> 1; if ( Y <= m ) ans ^= YQuery ( Y , lson , x ) ; else ans ^= YQuery ( Y , rson , x ) ; return ans ; } bool XQuery ( int X , int Y , int l , int r , int o ) { bool ans = 0 ; ans ^= YQuery ( Y , 1 , n , 1 , o ) ; if ( l == r ) return ans; int m = ( l + r ) >> 1 ; if ( X <= m ) ans ^= XQuery ( X , Y , lson ) ; else ans ^= XQuery ( X , Y , rson ) ; return ans ; } void work ( int m ) { clear ( sum , 0 ) ; char ch[ 5 ] ; int x1 , y1 , x2 , y2 , X , Y; while ( m -- ) { scanf ( "%s" , ch ) ; if ( ch[ 0 ] == 'C' ) { scanf ( "%d%d%d%d" , &x1 , &y1 , &x2 , &y2 ) ; XUpdate ( x1 , x2 , y1 , y2 , 1 , n , 1 ) ; } if ( ch[ 0 ] == 'Q' ) { scanf ( "%d%d" , &X, &Y ) ; printf ( "%d\n" , XQuery ( X , Y , 1 , n , 1 ) ) ; } } } int main () { int m , T ; for ( scanf ( "%d" , &T ) ; T ; -- T ) { scanf ( "%d%d" , &n , &m ) ; work ( m ) ; if ( T > 1 ) printf ( "\n" ) ; } return 0 ; }