高级数据结构第六章B . 矩阵操作

思路：

由于矩阵只由(0,1)组成，所以最后的值由改变次数决定。
用二维树状数组维护改变次数，区间修改单点求值。

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
ll ksm(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
const int inf = 0x3f3f3f3f;
#define PI acos(-1)

const int maxn=1100;

int lowbit(int x){
    return x&-x;
}

int n,T,tr[maxn][maxn];

void update(int x,int y,int val){
    for(;x<=n;x+=lowbit(x)){
        for(int ty=y;ty<=n;ty+=lowbit(ty)){
            tr[x][ty]+=val;
        }
    }
}

int qask(int x,int y){
    int res=0;
    for(;x;x-=lowbit(x))
        for(int ty=y;ty;ty-=lowbit(ty))
            res+=tr[x][ty];
    return res%2;
}

int main()
{
    n=read,T=read;
    while(T--){
        char op[2];
        cin>>op;
        if(op[0]=='C'){
            int x1=read,y1=read,x2=read,y2=read;
            update(x1,y1,1);
            update(x1,y2+1,-1);
            update(x2+1,y1,-1);
            update(x2+1,y2+1,1);
        }
        else{
            int x=read,y=read;
            printf("%d
",qask(x,y));
        }
    }
    return 0;
}

/*

**/