C. New Year and Domino

問題

$h \times w$の盤面$h,w \le 500$が与えられる。 各マスは空白か障害物があるかのどちらかである。 以下のクエリが$q \le 10^5$個与えられるので答えよ。

  • 座標$(t,l),(b,r)$が与えられる。盤面の中で、これらを頂点とする軸に並行な長方形の区間を考える。この区間中に、$1 \times 2$の長方形を置く置き方の総数を答えよ。

解法

累積和 + 包除原理。 ただし、区間からはみ出るように置く置き方を数えないように注意。

実装

累積和を3つに分けて持ってるの、もう少し上手くやれそうだなと感じる。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int h, w; cin >> h >> w;
    vector<string> s(h); repeat (y,h) cin >> s[y];
    vector<vector<int> > yacc(h+1, vector<int>(w+1));
    vector<vector<int> > xacc(h+1, vector<int>(w+1));
    vector<vector<int> > acc(h+1, vector<int>(w+1));
    repeat (y,h) {
        repeat (x,w) {
            if (y+1 < h) yacc[y+1][x+1] += (s[y][x] == '.' and s[y+1][x] == '.');
            if (x+1 < w) xacc[y+1][x+1] += (s[y][x] == '.' and s[y][x+1] == '.');
            acc[y+1][x+1] = yacc[y+1][x+1] + xacc[y+1][x+1];
        }
    }
    repeat (y,h) {
        repeat (x,w) {
            yacc[y+1][x+1] += yacc[y+1][x];
            xacc[y+1][x+1] += xacc[y][x+1];
            acc[y+1][x+1] += acc[y+1][x] + acc[y][x+1] - acc[y][x];
        }
    }
    int queries; cin >> queries;
    repeat (q, queries) {
        int t, l, b, r; cin >> t >> l >> b >> r;
        -- t; -- l;
        cout << acc[t][l] - acc[t][r] - acc[b][l] + acc[b][r] - (yacc[b][r] - yacc[b][l]) - (xacc[b][r] - xacc[t][r]) << endl;
    }
    return 0;
}