poj 2155（二维树状数组维护前缀和 求某个点被多少个矩形覆盖过）

思路：
要知道树状数组的本质是logn修改前缀和以及logn求出前缀和。
而这道题某个点的前缀和就是这个点被修改的次数。
没了。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <iterator>
#include <list>
#include <cstdio>
#include <iomanip>
#include <climits>
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=1100;
int tc,n,k,ft[maxn][maxn];
char s[5];
void update(int x, int y, int num){
    for(int i=x; i<=1005; i+=lowbit(i)){
        for(int j=y; j<=1005; j+=lowbit(j)){
            ft[i][j]+=num;
        }
    }
}
int getft(int x, int y){
    int sum=0;
    for(int i=x; i>0; i-=lowbit(i)){
        for(int j=y; j>0; j-=lowbit(j)){
            sum+=ft[i][j];
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &tc);
    while(tc--){
        memset(ft,0,sizeof(ft));
        scanf("%d%d", &n, &k);
        for(int i=0; i<k; ++i){
            scanf("%s", s);
            int x1,y1,x2,y2;
            if(s[0]=='C'){
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                update(x2+1,y2+1,1);
                update(x1,y2+1,-1);
                update(x2+1,y1,-1);
                update(x1,y1,1);
            } else{
                scanf("%d%d", &x1, &y1);
                int temp=getft(x1,y1);
                if(temp%2==0) puts("0");
                else puts("1");
            }
        }
        if(tc>0) puts("");
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

本文地址：https://blog.csdn.net/qq_43555854/article/details/108139157