AOJ 2842 たい焼きマスターと食べ盛り

二次元 BIT ライブラリ の verify をした

問題へのリンク

問題概要

H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの時間は T 秒である。

以下の Q 個のクエリに答えよ:

• type 0: 時刻 t に (h, w) にたこ焼きを配置する
• type 1: 時刻 t のときに (h, w) にたこ焼きが置いてあって、なおかつ焼き上がっていたらつまみ食いする
• type 2: 時刻 t において [h, h2] × [w, w2] の長方形領域に「焼き上がったたこ焼き」と「まだ焼き上がっていないたこ焼き」がそれぞれ何個ずつあるかを出力する

解法

クエリが来るごとに、「配置されたたこ焼きが焼き上がったかどうか」の確認はする。これは queue を使って管理できる。

そこさえ気をつければ、自然な二次元 BIT の問題と言える。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

template <class Abel> struct BIT2D {
    const Abel UNITY_SUM = 0;                     // to be set
    vector<vector<Abel> > dat;
    
    BIT2D(int n = 1, int m = 1) : dat(n + 1, vector<Abel>(m + 1, UNITY_SUM)) { }
    void init(int n, int m) { dat.assign(n + 1, vector<Abel>(m + 1, UNITY_SUM)); }
    
    /* add x on the point (a, b) */
    inline void add(int a, int b, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            for (int j = b; j < (int)dat[0].size(); j += j & -j)
                dat[i][j] = dat[i][j] + x;
    }
    
    inline Abel sum(int p, int q) {
        Abel res = UNITY_SUM;
        for (int i = p; i > 0; i -= i & -i)
            for (int j = q; j > 0; j -= j & -j)
                res = res + dat[i][j];
        return res;
    }
    
    /* a1 <= x < b1, a2 <= y < b2, 1-indexd */
    inline Abel sum(int a1, int a2, int b1, int b2) {
        return sum(b1-1, b2-1) - sum(a1-1, b2-1) - sum(b1-1, a2-1) + sum(a1-1, a2-1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) {
            for (int j = 1; j < (int)dat[0].size(); ++j)
                cout << sum(i, j, i+1, j+1) << ",";
            cout << endl;
        }
    }
};




typedef pair<int,int> pint; // zahyou
typedef pair<int,pint> ppint; // (time, zahyou)

int main() {
    int H, W, T, Q; cin >> H >> W >> T >> Q;
    BIT2D<int> fin(H, W), mada(H, W);
    queue<ppint> que;
    for (int query = 0; query < Q; ++query) {
        int t, c, h, w; cin >> t >> c >> h >> w;
        while (!que.empty()) {
            ppint pall = que.front();
            if (pall.first > t) break;
            que.pop();
            int x = pall.second.first, y = pall.second.second;
            mada.add(x, y, -1);
            fin.add(x, y, 1);
        }
        if (c == 0) {
            mada.add(h, w, 1);
            que.push(ppint(t+T, pint(h, w)));
        }
        else if (c == 1) {
            if (fin.sum(h, w, h+1, w+1) == 1) fin.add(h, w, -1);
        }
        else {
            int h2, w2; cin >> h2 >> w2;
            cout << fin.sum(h, w, h2+1, w2+1) << " " << mada.sum(h, w, h2+1, w2+1) << endl;
        }
    }
}