POJ - 2155 Matrix

题目链接：https://vjudge.net/problem/POJ-2155#author=happypeople

题目

给定 n* n 矩阵A，其元素为0或1. A [i][j] 表示第i行和第j列中的数字。最初全为0.

我们有两个操作:

1. C x1 y1 x2 y2（1 <= x1 <= x2 <= n，1 <= y1 <= y2 <= n）将左上角为(x1,y1)，右下角为(x2,y2)的矩阵翻转（0变成1，1变成0）。

2. Q x y（1 <= x，y <= n）查询A [x][y]，输出答案。

思路

二维树状数组，区间修改，单点查询模板题

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N,Q;
int tr[1010][1010];

int lowbit(int x){
    return x&-x;
}
void add(int x,int y,int v){
    for(int i = x;i<=N;i += lowbit(i))
        for(int j = y;j<=N;j += lowbit(j))
            tr[i][j] += v;
}
int query(int x,int y){
    int sum = 0;
    for(int i = x;i>=1;i -= lowbit(i))
        for(int j = y;j>=1;j -= lowbit(j))
            sum += tr[i][j];
    return sum;
}
int main(){
    ios;
    cin>>T;
    int tag = 0;
    while(T--){
        if(tag) cout<<'\n';tag = 1;
        memset(tr,0,sizeof tr);
        cin>>N>>Q;
        string op;int x1,y1,x2,y2;
        while(Q--){
            cin>>op;
            if(op == "C"){
                cin>>x1>>y1>>x2>>y2;
                add(x1,y1,+1);
                add(x1,y2+1,-1);
                add(x2+1,y1,-1);
                add(x2+1,y2+1,+1);
            }else{
                cin>>x1>>y1;
                cout<<query(x1,y1) % 2 <<'\n';
            }
        }
    }
    return 0;
}