verify/Datastructure_2dbit.test.cpp

View this file on GitHub
Last update: 2025-02-19 12:40:07+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#include "../Utility/template.hpp"
#include "../Datastructure/2dbit.hpp"

int main() {
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    bit2d<ll> J(h, w);
    bit2d<ll> O(h, w);
    bit2d<ll> I(h, w);


    rep(i, 0, h) rep(j, 0, w) {
        char a;
        cin >> a;
        if(a=='J') J.add(i, j, 1);
        if(a=='O') O.add(i, j, 1);
        if(a=='I') I.add(i, j, 1);
    }



    while(k--) {
        int sy, sx, ty, tx;
        cin >> sy >> sx >> ty >> tx;
        sy--, sx--;
        cout << J.prod(sy, ty, sx, tx) << " ";
        cout << O.prod(sy, ty, sx, tx) << " ";
        cout << I.prod(sy, ty, sx, tx) << endl;

    }
	

}

#line 1 "verify/Datastructure_2dbit.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/2dbit.hpp"
TT struct bit2d {
    int h, w;
    vec<vec<T>> dat;

    bit2d(int H, int W) : h(H), w(W) {
        dat = vec<vec<T>>(h, vec<T>(w, 0));
    }

    void add(int y, int x, T v) {
        assert(0 <= y && y < h);
        assert(0 <= x && x < w);
        for( ; y < h; y |= y + 1) {
            for(int b = x; b < w; b |= b + 1) {
                dat[y][b] += v;
            }
        }
    }

    T prod(int y, int x) const {
        T res = 0;
        y--, x--;
        for( ; y >= 0; y = (y & (y + 1)) - 1) {
            for(int b = x; b >= 0; b = (b & (b + 1)) - 1) {
                res += dat[y][b];
            }
        }
        return res;
    }

    T prod(int sy, int ty, int sx, int tx) const {
        assert(0 <= sy && sy <= ty && ty <= h);
        assert(0 <= sx && sx <= tx && tx <= w);

        T res = prod(ty, tx);
        res -= prod(sy, tx);
        res -= prod(ty, sx);
        res += prod(sy, sx);
        return res;
    }
};
#line 4 "verify/Datastructure_2dbit.test.cpp"

int main() {
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    bit2d<ll> J(h, w);
    bit2d<ll> O(h, w);
    bit2d<ll> I(h, w);


    rep(i, 0, h) rep(j, 0, w) {
        char a;
        cin >> a;
        if(a=='J') J.add(i, j, 1);
        if(a=='O') O.add(i, j, 1);
        if(a=='I') I.add(i, j, 1);
    }



    while(k--) {
        int sy, sx, ty, tx;
        cin >> sy >> sx >> ty >> tx;
        sy--, sx--;
        cout << J.prod(sy, ty, sx, tx) << " ";
        cout << O.prod(sy, ty, sx, tx) << " ";
        cout << I.prod(sy, ty, sx, tx) << endl;

    }
	

}