Good Bye 2015 C. New Year and Domino

問題

codeforces.com

解法

長いですが, 大事なことは
「長方形区間から飛び出すタイルは右側か下側にしかないので計算量は O(Q(W+H))」ということだけです。

タイルの埋め方は, (y, x) と (y+1, x) を覆うようにタイルを埋める(下方向に埋める)か, (y, x) と (y, x+1) を埋めるようにタイルを埋める(右方向に埋める)かのどちらかです。
ということで, あらかじめ各頂点 (y, x) について, 右方向, 下方向に埋められるタイルを調べておきます。例えば, 問題文に書かれているサンプル 1 つ目の図だと, (0, 0) からは下方向, 右方向ともに埋めることが出来, (0, 3) からは下方向のみ埋めることが出来ます。

この情報を用いて, total[y][x] = (左上が(0, 0) で右下が (y, x) であるような長方形区間の間に, 埋めることが出来るタイルの数はいくつあるか) を求めます。ただ, ここでは範囲になっている長方形を飛び出すことも許します。例えば, total[0][3] を考えると, 本当は 3 個のタイルしか埋められませんが, 頂点 (0, 0), (0, 2), (0, 3) から下方向にタイルを埋めることも許します。

ただ, 入力で与えられている長方形よりも外にタイルが飛び出すのは NG です。例えば total[2][7] を考えた時, 頂点 (2, 7) や頂点 (1, 7) から右方向にタイルを埋めようとするのは NG です。

total が分かれば, よくある感じで任意の長方形区間 (r1, c1, r2, c2) の間に入っている, 埋められるタイルの数(ただし長方形から飛び出すのを許す) がわかります。下のソースコードで getSum でやってるやつです。

これだとある長方形区間が与えられた時, 長方形から飛び出すタイルも余計に数えてしまっていますが, タイルが飛び出すことがありえるのは, 長方形の右辺, 下辺の部分からのみなので, 飛び出すタイルは O(H+W) で数えられます。よって, 計算量は O(Q(H+W)) となり, 時間内に答えを求めることが出来ます。

const int MAXH = 555;
string board[MAXH];
vector<pii> adj[MAXH][MAXH];
int total[MAXH][MAXH];

int getSum(int y1, int x1, int y2, int x2) {
    return total[y1][x1] - total[y2-1][x1] - total[y1][x2-1] + total[y2-1][x2-1];
}

bool inrange(int r1, int c1, int r2, int c2, int y, int x) {
    return r1 <= y && y <= r2 && c1 <= x && x <= c2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> board[i];
    for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) {
        if (board[y][x] == '#') continue;
        for (int k = 0; k < 2; k++) {
            int ny = y+dy[k];
            int nx = x+dx[k];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if (board[ny][nx] == '#') continue;
            adj[y][x].emplace_back(ny, nx);
        }
    }
    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
        total[i][j] = total[i][j-1] + total[i-1][j] - total[i-1][j-1] + adj[i-1][j-1].size();
    }
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        int ans = getSum(r2, c2, r1, c1);
        r1--; c1--; r2--; c2--;
        for (int x = c1; x < c2; x++) {
            for (pii p : adj[r2][x]) {
                if (!inrange(r1, c1, r2, c2, p.first, p.second)) ans--;
            }
        }
        for (int y = r1; y < r2; y++) {
            for (pii p : adj[y][c2]) {
                if (!inrange(r1, c1, r2, c2, p.first, p.second)) ans--;
            }
        }
        for (pii p : adj[r2][c2]) {
            if (!inrange(r1, c1, r2, c2, p.first, p.second)) ans--;
        }
        cout << ans << endl;
    }
    return 0;
}