Atcoder AGC #015 C. Nuske vs Phantom Thnook

Atcoder AGC #015 C. Nuske vs Phantom Thnook

C: Nuske vs Phantom Thnook - AtCoder Grand Contest 015 | AtCoder

実はグラフの問題だったという感じがして好きな問題。

色が塗られたグリッドが与えられる。その上下左右について辺を共有するマス同士を連結であると呼ぶと、連結な部分については、木のようになっている。このとき、長方形を表すクエリに対して、その中に何個の連結成分があるかを答えていく問題。愚直に数えていては当然間に合わないので、累積和を使うことは多分みんな思いつく。が、そこからが長かった。次の森の性質に気付けるかが重要であった（そもそも木であることになんの意味があるのか数時間気づけなかった）。
森に関して、その連結成分の数をu, 辺の数をm, 頂点の数をnとすると、n - m = vとなる。
木について辺の数がn - 1であることを考えれば割と自明ではある。というか問題が解けた後に気付いたんだけど。
このことを利用すると、長方形が与えられた時に、累積和を用いてその中に含まれる塗られたグリッドの総数（頂点数nの個数に相当する）を求め、さらにその中に含まれる塗られたグリッド同士を仕切る部分の総数（辺の数mに相当する）を求めることで、連結成分の個数が求められる。

グラフ理論しっかりやりたい感が強くなった。

#include "bits/stdc++.h"
using namespace std;

int main() {
        int h, w, q;
        cin >> h >> w >> q;
        vector<string> s(h);
        for (int i = 0; i < h; i ++) cin >> s[i];
        vector<vector<int>> t(h, vector<int> (w));
        for (int i = 0; i < h; i ++) {
                for (int j = 0; j < w; j ++) {
                        if (s[i][j] == '1') t[i][j] = 1;
                        else t[i][j] = 0;
                }
        }
        vector<vector<int>> ver(h, vector<int> (w, 0));
        vector<vector<int>> hor(h, vector<int> (w, 0));
        for (int y = 0; y < h; y ++) {
                for (int x = 0; x < w; x ++) {
                        if (x + 1 < w) if (t[y][x] && t[y][x + 1]) hor[y][x] = 1;
                        if (y + 1 < h) if (t[y][x] && t[y + 1][x]) ver[y][x] = 1;
                }
        }
        for (int x = 0; x < w; x ++) {
                for (int y = 1; y < h; y ++) {
                        t[y][x] += t[y - 1][x];
                        ver[y][x] += ver[y - 1][x];
                        hor[y][x] += hor[y - 1][x];
                }
        }
        for (int y = 0; y < h; y ++) {
                for (int x = 1; x < w; x ++) {
                        t[y][x] += t[y][x - 1];
                        ver[y][x] += ver[y][x - 1];
                        hor[y][x] += hor[y][x - 1];
                }
        }
        while (q --) {
                int y1, x1, y2, x2;
                cin >> y1 >> x1 >> y2 >> x2;
                y1 --, x1 --, y2 --, x2 --;
                int sum = t[y2][x2] - (y1 - 1 >= 0 ? t[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? t[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? t[y1 - 1][x1 - 1] : 0));
                int versum = 0;
                y2 --;
                if (y1 <= y2) {
                        versum = ver[y2][x2] - (y1 - 1 >= 0 ? ver[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? ver[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? ver[y1 - 1][x1 - 1] : 0));
                }
                y2 ++;
                int horsum = 0;
                x2 --;
                if (x1 <= x2) {
                        horsum = hor[y2][x2] - (y1 - 1 >= 0 ? hor[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? hor[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? hor[y1 - 1][x1 - 1] : 0));
                }
                x2 ++;
                cout << sum - versum - horsum << endl;
        }
        return 0;
}