题解 | #如何才能穿过传送门#B题二维树状数组

发现此题异或等价于加法，区间求异或和等与区间求和%2的结果，因此可以直接用二维树状数组模板。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <queue>

using namespace std;
#define endl '\n'
#define ll long long
int n,m;
const int maxn = 1e3 + 5;
int lowbit(int x){
    return -x & x;
}
int t[5][maxn][maxn];
ll get(ll z,ll x,ll y)
{
    ll ans=0;
    for(ll i=x;i;i-=lowbit(i)) for(ll j=y;j;j-=lowbit(j)) ans+=t[z][i][j];
    return ans;
}
ll sum(ll x,ll y)
{
    return (((x+1)*(y+1)*get(0,x,y))-((x+1)*get(2,x,y))-((y+1)*get(1,x,y))+get(3,x,y));
}
void put(ll z,ll x,ll y,ll w)
{
    for(ll i=x;i<=n;i+=lowbit(i)) for(ll j=y;j<=m;j+=lowbit(j)) t[z][i][j]+=w;
}
void ins(ll x,ll y,ll w)
{
    put(0,x,y,w);
    put(1,x,y,w*x);
    put(2,x,y,w*y);
    put(3,x,y,w*x*y);
}
void add(int x1,int y1,int x2,int y2,int z)
{
    ins(x1,y1,z);ins(x1,y2+1,-z);ins(x2+1,y1,-z);ins(x2+1,y2+1,z);
}
int query(int x1,int y1,int x2,int y2)
{
    return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
}
void solve(){
    int q;
    cin >> n >> m >> q;
    while (q --){
        int op,x1,y1,x2,y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        int len = (x2 - x1 + 1) * (y2 - y1 + 1);
        if (op == 1){
            add(x1,y1,x2,y2,1);
        }
        else{
            int sum = query(x1,y1,x2,y2);
            if (sum  % 2) cout << 1 << endl;
            else cout << 0 << endl;
        }

    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t = 1;
//    cin >> t;
    while (t--) solve();

}