JOI 10 本選 Planetary Exploration ( 二次元BIT )

Planetary Exploration | Aizu Online Judge
なにも考えずに一番先に頭から出たのが二次元BIT。普通にprefix sumでもいけるけど、BITは応用が効くからこれで。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 3;
const int MAXM = 1000 + 3;
const int MAXK = 1e5 + 5;

int n, m, k;
char G[ MAXN ][ MAXM ];

struct BIT{
    int dat[ MAXN ][ MAXM ];
    void update(int x, int y, int v){
        for(int i = x; i <= n; i += i & -i)
            for(int j = y; j <= m; j += j & -j)
                dat[ i ][ j ] += v;
    }
    int qsum(int x, int y){
        int res = 0;
        for(int i = x; i > 0; i -= i & -i)
            for(int j = y; j > 0; j -= j & -j)
                res += dat[ i ][ j ];
        return res;
    }
    int qsum(int x0, int y0, int x1, int y1){
        return qsum( x1, y1 ) - qsum( x0 - 1, y1 ) - qsum( x1, y0 - 1 ) + qsum( x0 - 1, y0 - 1 );
    }
} jbit, obit, ibit;

void solve(){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            if( G[ i ][ j ] == 'J' )
                jbit.update( i, j, 1 );
            if( G[ i ][ j ] == 'O' )
                obit.update( i, j, 1 );
            if( G[ i ][ j ] == 'I' )
                ibit.update( i, j, 1 );
        }
    while( k-- ){
        int x0, y0, x1, y1; scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
        int jcnt = jbit.qsum( x0, y0, x1, y1 );
        int ocnt = obit.qsum( x0, y0, x1, y1 );
        int icnt = ibit.qsum( x0, y0, x1, y1 );
        printf("%d %d %d\n", jcnt, ocnt, icnt);
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%s", G[ i ] + 1);
    solve();
    return 0;
}