Brief description:
… 給定一個 0/1 矩陣,初始全是 0,動態維護以下操作。
- C x1 y1 x2 y2: 將一個子矩陣取反。
- Q x y: 詢問單個位置的狀態。
Analysis:
… 略(二維樹狀數組。。。
const int N = 1001; bool C[N][N]; int n, m; void Modify(int x, int y){ while (x > 0){ for (int t = y; t > 0; t -= low_bit(t)) C[x][t] ^= 1; x -= low_bit(x); } } bool Query(int x, int y){ bool res = false; while (x <= n){ for (int t = y; t <= n; t += low_bit(t)) res ^= C[x][t]; x += low_bit(x); } return res; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif Rush{ int x1, y1, x2, y2; char cmd; RST(C); RD(n); DO_C(RD()){ RC(cmd); if (cmd =='C'){ RD(x1, y1, x2, y2); Modify(x2, y2), Modify(x2, y1-1), Modify(x1-1, y2), Modify(x1-1, y1-1); } else { RD(x1, y1); OT(Query(x1, y1)); } } puts(""); } }