Matrix POJ - 2155

解法

二维树状数组直接写即可，变反写成+1，最后查询的时候%2就行

代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}

//--------------------------------------------
int T,N,Q;
int tr[1010][1010];
void init(){
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=N;j++){
            tr[i][j] = 0;
        }
    }
}
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(){
    // debug_in;

    read(T);
    while(T--){
        read(N,Q);
        init();
        while(Q--){
            char op;
            scanf(" %c",&op);
            if(op == 'C'){
                int x1,y1,x2,y2;
                read(x1,y1,x2,y2);
                add(x1,y1,+1);
                add(x2+1,y1,-1);
                add(x1,y2+1,-1);
                add(x2+1,y2+1,+1);
            }else{
                int x,y;
                read(x,y);
                int ans = query(x,y);
                printf("%d\n",ans%2);
            }
        }
        if(T) puts("");
    }


    return 0;
}

线段树套线段树写法

不过自己还不太懂，照猫画虎写的

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}

//--------------------------------------------
int T,N,Q;
int x1,x2,y1,y2;
struct Seg
{
    #define lson u<<1
    #define rson u<<1|1

    bool tr[1010*4][1010*4];
    void modify_sub(int l,int r,int id,int u = 1){
        if(l == y1 && r == y2){
            tr[id][u] ^=1;
        }else{
            int mid = (l+r)>>1;
            if(y1 <= mid) modify_sub(l,mid,id,lson);
            if(y2 > mid) modify_sub(mid+1,r,id,rson);
        }
    }
    void modify(int l,int r,int sl,int sr,int u = 1){
        if(l == x1 && r == x2){
            modify_sub(sl,sl,u);
        }else{
            int mid = (l+r)>>1;
            if(l<= mid) modify(l,mid,sl,sr,lson);
            if(r > mid) modify(mid+1,r,sl,sr,rson);
        }
    }
    int query_sub(int l,int r,int id,int u = 1){
        int ans = 0;
        if(l == y1 && r == y2){
            ans ^= tr[id][u];
        }else{
            int mid = (l+r)>>1;
            if(l<=mid) ans ^= query_sub(l,mid,id,lson);
            else ans ^= query_sub(mid+1,r,id,rson);
        }
        return ans;
    }
    int query(int l,int r,int sl,int sr,int u = 1){
        int ans = 0;
        if(l >= x1 && r <= x2){
            ans ^= query_sub(sl,sr,u);
        }else{
            int mid = (l+r)>>1;
            if(l<=mid) ans ^= query(l,mid,sl,sr,lson);
            if(r>mid) ans ^= query(mid+1,r,sl,sr,rson);
        }
        return ans;
    }

}seg;

int main(){
    debug_in;

    read(T);
    while(T--){
        read(N,Q);
        for(int i = 1;i<=4*N;i++) for(int j = 1;j<=4*N;j++) seg.tr[i][j] = 0;
        while(Q--){
            char op;
            scanf(" %c",&op);
            if(op == 'C'){
                int x1,y1,x2,y2; read(x1,y1,x2,y2);
                seg.modify(1,N,1,N);
            }else{
                int x,y; read(x,y);
                int ans = seg.query(1,N,1,N);
                printf("%d\n",ans);
            }
        }
        if(T) puts("");
    }


    return 0;
}