首页 > 代码库 > POJ 2155 Matrix (二维线段树)
POJ 2155 Matrix (二维线段树)
http://poj.org/problem?id=2155
Matrix
Description Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N). 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 the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case. 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 For each querying output one line, which has an integer representing A[x, y]. 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 Monthly,Lou Tiancheng |
谨以此题来祭我的第一道二维线段树!
没有30道线段树的基础不要碰二维线段树!
题意:
给出一个N×N的零矩阵,有两种操作:C x1 y1 x2 y2 是将(x1,y1) (x2,y2)对应范围内的矩阵中的0/1互换,Q x y是查询(x,y)位置元素的值。
分析:
0/1互换即异或操作,朴素的算法时间复杂度显然不够。如果是一维的坐标轴显然可以用线段树解,但这是一个二维的,那么就要用到二维线段树了。
曾经的我天真地认为二维线段树就是把一个矩形直接分成4份:左上、右上、左下、右下,后来遇到一个三维的题目我还YY出了把立方体分成8份来解(当然没过啦,而且标程也不是用线段树的)。 实际上,二维线段树是先将X坐标二分,然后再将Y轴二分。第二维维护的也是一棵线段树,没错,二维线段树就是线段树套线段树!二分,再二分!
本题每次更新的时候先操作X轴,操作到对应区间时再对Y轴进行操作,从二维到一维,达到降维的效果。
查询时每次查到在所在的X区间内时都要对Y轴进行查询。
如果对线段树理解较深,相信对此不难理解。
详情请见代码(个人习惯维护左闭右开的区间,下标从0开始,所以有些调整):
#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<ctime> #include<cctype> #include<cmath> #include<string> #include<cstring> #include<stack> #include<queue> #include<list> #include<vector> #include<map> #include<set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm #define maxn 1007 using namespace std; int XOR[maxn<<2][maxn<<2]; int n,m; //update_1d() 更新一维 //[a,b)表示当前在一维操作的区间(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(Y方向),k_2d表示二维对应的节点标号 void update_1d(int a,int b,int k,int l,int r,int k_2d) { if (b<=l || r<=a) return ; if (a<=l && r<=b) { XOR[k_2d][k]^=1; } else { update_1d(a,b,k*2+1,l,l+r>>1,k_2d); update_1d(a,b,k*2+2,l+r>>1,r,k_2d); } } //update_2d() 更新二维 //[a,b)表示当前在二维操作的区间(X方向),[y1,y2)表示将要在一维操作的区间(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(X方向) void update_2d(int a,int b,int y1,int y2,int k,int l,int r) { if (b<=l || r<=a) return ; if (a<=l && r<=b) { update_1d(y1,y2,0,0,n,k); } else { update_2d(a,b,y1,y2,k*2+1,l,l+r>>1); update_2d(a,b,y1,y2,k*2+2,l+r>>1,r); } } //query_1d() 查询一维 //p表示当前在一维查询的位置(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(Y方向),k_2d表示二维对应的节点标号 int query_1d(int p,int k,int l,int r,int k_2d) { if (r-l==1) return XOR[k_2d][k]; int m=l+r>>1; if (p<m) return XOR[k_2d][k]^query_1d(p,k*2+1,l,m,k_2d); else return XOR[k_2d][k]^query_1d(p,k*2+2,m,r,k_2d); } //query_2d() 查询二维 //px表示当前在二维查询的位置(X方向),py表示将要在一维查询的位置(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(X方向) int query_2d(int px,int py,int k,int l,int r) { int res=query_1d(py,0,0,n,k);// attention please! if (r-l==1) return res; int m=l+r>>1; if (px<m) return res^query_2d(px,py,k*2+1,l,m); else return res^query_2d(px,py,k*2+2,m,r); } int main() { #ifndef ONLINE_JUDGE freopen("/home/fcbruce/文档/code/t","r",stdin); #endif // ONLINE_JUDGE int T_T; scanf("%d",&T_T); while (T_T--) { scanf("%d %d",&n,&m); memset(XOR,0,sizeof XOR); for (int i=0;i<m;i++) { char op; int x1,x2,y1,y2; getchar(); op=getchar(); if (op=='C') { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); x1--;y1--; update_2d(x1,x2,y1,y2,0,0,n); } else { scanf("%d %d",&x1,&y1); x1--;y1--; printf("%d\n",query_2d(x1,y1,0,0,n)); } } if (T_T) putchar('\n'); //因为这个PE一发 } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。