POJ 2155 Matrix 二维线段树

题目：

http://poj.org/problem?id=2155

题意：

有一个初始元素均为0的n∗n矩阵，有下面两种操作：

C x1 y1 x2 y2 以x1 y1为左上角，以x2 y2为右上角，把在这个范围内的矩阵元素取反，0变1，0变0 Q x y查询矩阵中x y位置的元素

思路：

二维线段树题目，二维树状数组也可以。用一个线段树管理行，这个线段树内的点都是一个线段树，管理行内相应的列。看了好多二维线段树代码，想找一个通用式的模板，奈何大家写的基本都不怎么通用，自己尝试着写了一个，在第二维线段树里面进行lazy操作，比较慢。

//1100ms #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000 + 10, INF = 0x3f3f3f3f; bool g[N<<2][N<<2]; int n, m; void updatey(int ly, int ry, int L, int R, int ky, int kx) { if(ly <= L && R <= ry) { g[kx][ky] ^= 1; return; } int mid = (L + R) >> 1; if(ly <= mid) updatey(ly, ry, L, mid, ky << 1, kx); if(ry > mid) updatey(ly, ry, mid + 1, R, ky << 1|1, kx); } void updatex(int lx, int rx, int ly, int ry, int L, int R, int kx) { if(lx <= L && R <= rx) { updatey(ly, ry, 1, n, 1, kx); return; } int mid = (L + R) >> 1; if(lx <= mid) updatex(lx, rx, ly, ry, L, mid, kx << 1); if(rx > mid) updatex(lx, rx, ly, ry, mid + 1, R, kx << 1|1); } int queryy(int y, int L, int R, int ky, int kx) { int ans = g[kx][ky]; if(L == R) return ans; int mid = (L + R) >> 1; if(y <= mid) ans ^= queryy(y, L, mid, ky << 1, kx); else ans ^= queryy(y, mid + 1, R, ky << 1|1, kx); return ans; } int queryx(int x, int y, int L, int R, int kx) { int ans = queryy(y, 1, n, 1, kx); if(L == R) return ans; int mid = (L + R) >> 1; if(x <= mid) ans ^= queryx(x, y, L, mid, kx << 1); else ans ^= queryx(x, y, mid + 1, R, kx << 1|1); return ans; } int main() { int t; scanf("%d", &t); while(t--) { memset(g, 0, sizeof g); scanf("%d%d", &n, &m); int x1, y1, x2, y2; char op; for(int i = 1; i <= m; i++) { scanf(" %c", &op); if(op == 'C') { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); updatex(x1, x2, y1, y2, 1, n, 1); } else { scanf("%d%d", &x1, &y1); printf("%d\n", queryx(x1, y1, 1, n, 1)); } } if(t) printf("\n"); } return 0; }

自己写的通用式模板（其实也不怎么通用）：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000 + 10, INF = 0x3f3f3f3f; bool val[N<<2][N<<2], lazy[N<<2][N<<2]; int n, m; void push_downy(int ky, int kx) { if(lazy[kx][ky]) { val[kx][ky<<1] ^= lazy[kx][ky], lazy[kx][ky<<1] ^= lazy[kx][ky]; val[kx][ky<<1|1] ^= lazy[kx][ky], lazy[kx][ky<<1|1] ^= lazy[kx][ky]; lazy[kx][ky] = 0; } } void updatey(int ly, int ry, int L, int R, int ky, int kx) { if(ly <= L && R <= ry) { val[kx][ky] ^= 1; lazy[kx][ky] ^= 1; return; } push_downy(ky, kx); int mid = (L + R) >> 1; if(ly <= mid) updatey(ly, ry, L, mid, ky << 1, kx); if(ry > mid) updatey(ly, ry, mid + 1, R, ky << 1|1, kx); } void updatex(int lx, int rx, int ly, int ry, int L, int R, int kx) { if(lx <= L && R <= rx) { updatey(ly, ry, 1, n, 1, kx); return; } int mid = (L + R) >> 1; if(lx <= mid) updatex(lx, rx, ly, ry, L, mid, kx << 1); if(rx > mid) updatex(lx, rx, ly, ry, mid + 1, R, kx << 1|1); } int queryy(int y, int L, int R, int ky, int kx) { int ans = 0; if(L == R) { return ans ^= val[kx][ky]; } push_downy(ky, kx); int mid = (L + R) >> 1; if(y <= mid) ans ^= queryy(y, L, mid, ky << 1, kx); else ans ^= queryy(y, mid + 1, R, ky << 1|1, kx); return ans; } int queryx(int x, int y, int L, int R, int kx) { int ans = queryy(y, 1, n, 1, kx); if(L == R) return ans; int mid = (L + R) >> 1; if(x <= mid) ans ^= queryx(x, y, L, mid, kx << 1); else ans ^= queryx(x, y, mid + 1, R, kx << 1|1); return ans; } int main() { int t; scanf("%d", &t); while(t--) { memset(val, 0, sizeof val); memset(lazy, 0, sizeof lazy); scanf("%d%d", &n, &m); char op; int x1, y1, x2, y2; for(int i = 1; i <= m; i++) { scanf(" %c", &op); if(op == 'C') { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); updatex(x1, x2, y1, y2, 1, n, 1); } else { scanf("%d%d", &x1, &y1); printf("%d\n", queryx(x1, y1, 1, n, 1)); } } if(t) printf("\n"); } return 0; }