JOI 2011 本選 「惑星探査」 AOJ0560 (Planetary Exploration) C++

想定解は二次元累積和なのですが二次元BITの練習のため二次元BITで解いてみた。
本番では絶対こんな手法は使わない。

計算量はO(K*logM*logN)でだいたいO(10^7)ぐらいなので間に合う。

#include <bits/stdc++.h>
using namespace std;
 
int bit[3][1010][1010];
int m,n,k;
 
int ch(char x){
    int res = 2;
    if(x == 'J'){
        res = 0;
    }else if(x == 'O'){
        res = 1;
    }
 
    return res;
}
 
void add(int a,int b,int ban){
 
    for(int i = a;i <= m;i += i & -i){
        for(int j = b;j <= n;j += j & -j){
            bit[ban][i][j]++;
        }
    }
}
 
int sum(int a,int b,int ban){
    int res = 0;
     
    for(int i = a;i > 0;i -= i & -i){
        for(int j = b;j > 0;j -= j & -j){
            res += bit[ban][i][j];
        }
    }
    return res;
}
 
int main(){
    scanf("%d%d%d",&m,&n,&k);
 
    for(int i = 1;i <= m;i++){
        char t[1004];
        scanf("%s",t);
        for(int j = 1;j <= n;j++){
            int tikei = ch(t[j-1]);
            add(i,j,tikei);
        }
    }
 
    while(k--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
 
        for(int i = 0;i < 3;i++){
            printf("%d",sum(c,d,i)-sum(a-1,d,i)-sum(c,b-1,i)+sum(a-1,b-1,i));
            if(i <= 1){
                printf(" ");
            }
        }
        printf("\n");
    }
 
    return 0;
}