Solution AGC015C

Analysis

The key observation is this sentence:

For every pair of two blue square $a$ and $b$, there is at most one path that starts from $a$, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches $b$, without traversing the same square more than once.

This could be rewritten as

For each two node, only one simple path connects them

which is a definition of a forest.

With forests, we have the simple conclusion that, $N_{\mathrm{Conn}}=|V|-|E|$. This is intuitive in that, if the forest is reduced to a tree, then rhs is $1$, which is yet another definition of a tree.

Based on this observation, we can use 2D prefix sum to maintain the rectangular sum of nodes, vertical edges and horizontal edges. Note that edges cannot lead to nodes out of the boundary.

Code

const int N = 2020;
int sumv[N][N], sumh[N][N], sumn[N][N];
char s[N][N];
int n, m, q;
void Main() {
    rd(n, m, q);
    repn(i, n) repn(j, m) {
        cin >> s[i][j];
        sumv[i][j] = sumv[i - 1][j] + sumv[i][j - 1] - sumv[i - 1][j - 1] + (s[i][j] == '1' && s[i][j - 1] == '1');
        sumh[i][j] = sumh[i - 1][j] + sumh[i][j - 1] - sumh[i - 1][j - 1] + (s[i][j] == '1' && s[i - 1][j] == '1');
        sumn[i][j] = sumn[i - 1][j] + sumn[i][j - 1] - sumn[i - 1][j - 1] + (s[i][j] == '1');
    }
    while (q--) {
        int x1, y1, x2, y2;
        rd(x1, y1, x2, y2);
        cout << (sumn[x2][y2] - sumn[x1 - 1][y2] - sumn[x2][y1 - 1] + sumn[x1 - 1][y1 - 1]) -
                (sumh[x2][y2] - sumh[x1][y2] - sumh[x2][y1 - 1] + sumh[x1][y1 - 1]) -
                (sumv[x2][y2] - sumv[x1 - 1][y2] - sumv[x2][y1] + sumv[x1 - 1][y1]) << endl;
    }
}

Comment

Take note of the unconventional statements in the problem. In this problem, the given connected components are special in that they form several trees, and this is the key observation that ultimately leads to the solution of this problem.