题解：P7970 [KSN2021] Binary Sea

· · 题解

好想不好写的做法。

题解

首先，在森林中，连通块数量等于点数量减边数量，应用到图上就是点的数量减去所有生成树边数量的和。

点的数量是好求的，就是这个矩形有多少个黑点，传统数位动态规划即可。

对于生成树边的数量，考虑统计这个矩形中包含多少 1\times2 和 2\times1 的子矩形并且这个子矩形里面都是黑点，仔细思考不难得出两者是相等的，因为原图不可能会包含一个 2\times2 的子矩形，使得这里面都是黑点。

而 1\times2 和 2\times1 是对称的，只需要把整个矩形旋转 90 度即可，因此下文主要说明怎么统计一个子矩形中有多少 1\times2 的黑块即可。

形式化地，我们需要求解数对 (i,j) 的个数满足：

难点在于维护 j+1，这通常需要一个进位标记。考虑从高位到低位做，设 dp(dig, S, jw)，具体表述如下：

接下来考虑怎么维护 jw 状态以及相关的转移，尝试分类讨论：

而边界情况，即 dig=-1 的时候，我们可以认为一个二进制数加一一定会导致第 -1 位进位，所以 dp(-1, S,1)=1, dp(-1,S,0)=0。

和 S 相关的转移正常做即可。

时间复杂度 O(Q \log \max(N,M))，DP 状态带来的常数是 2^5，DP 转移带来的常数是 2^2，因为还要把矩阵旋转 90 度再做一遍，所以总常数大约是 2^7，比较极限，实测记忆化过不了，需要一定卡常。

当然也可以写二维前缀和，理论可以优化掉 \dfrac{1}{4} 的常数，不过需要注意一点细节。但本人测试似乎没有取到好的效果。

代码

这里没有用二维前缀和。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int L1, L2, R1, R2;
int dp[32][2][2][2][2][2], dp2[2][2][2][2][2];

inline int get1(int i, int lli, int lri, int llj, int lrj, int jw) { 
    if (i == -1) return jw == 1;
    return dp[i & 1][lli][lri][llj][lrj][jw];
}

inline int solve(int l1, int r1, int l2, int r2) {
    L1 = l1;
    L2 = l2;
    R1 = r1;
    R2 = r2 - 1;
    if (L2 > R2 || R2 < 0) {
        return 0;
    }
    memset(dp, 255, sizeof(dp));
    for (int i = 0; i <= 30; ++i) for (int lli = 0; lli <= 1; ++lli) for (int lri = 0; lri <= 1; ++lri)
        for (int llj = 0; llj <= 1; ++llj) for (int lrj = 0; lrj <= 1; ++lrj) for (int jw = 0; jw <= 1; ++jw) {
            int dli = (L1 >> i) & 1, dlj = (L2 >> i) & 1;
            int dri = (R1 >> i) & 1, drj = (R2 >> i) & 1;
            int ans = 0;
            for (int ni = (lli ? 0 : dli); ni <= (lri ? 1 : dri); ++ni) {
                for (int nj = (llj ? 0 : dlj); nj <= (lrj ? 1 : drj); ++nj) {
                    if ((ni & nj) || (ni & (nj ^ jw))) continue;
                    if (jw == 1 && nj == 0) continue;
                    ans += get1(i - 1, lli || (ni ^ dli), lri || (ni ^ dri), llj || (nj ^ dlj), lrj || (nj ^ drj), jw); 
                    if (jw == 0 && nj == 0 && ni == 0) ans += get1(i - 1, lli || (ni ^ dli), lri || (ni ^ dri), llj || (nj ^ dlj), lrj || (nj ^ drj), 1); 
                }
            }
            dp[i & 1][lli][lri][llj][lrj][jw] = ans;
        }
    return get1(0, 0, 0, 0, 0, 0); 
}

inline int get2(int i,  int lli, int lri, int llj, int lrj) {
    if (i == -1) return 1;
    return dp2[i & 1][lli][lri][llj][lrj];
}

inline int solve2(int l1, int r1, int l2, int r2) {
    if (r1 < 0 || r2 < 0) return 0;
    L1 = l1;
    L2 = l2;
    R1 = r1;
    R2 = r2;
    for (int i = 0; i <= 30; ++i) for (int lli = 0; lli <= 1; ++lli) for (int lri = 0; lri <= 1; ++lri)
        for (int llj = 0; llj <= 1; ++llj) for (int lrj = 0; lrj <= 1; ++lrj) {
            int ans = 0;
            int dli = (L1 >> i) & 1, dlj = (L2 >> i) & 1;
            int dri = (R1 >> i) & 1, drj = (R2 >> i) & 1;
            for (int ni = (lli ? 0 : dli); ni <= (lri ? 1 : dri); ++ni) {
                for (int nj = (llj ? 0 : dlj); nj <= (lrj ? 1 : drj); ++nj) {
                    if (ni & nj) continue;
                    ans += get2(i - 1, lli || (ni ^ dli), lri || (ni ^ dri), llj || (nj ^ dlj), lrj || (nj ^ drj));
                }
            }
            dp2[i & 1][lli][lri][llj][lrj] = ans;
        }
    return get2(0, 0, 0, 0, 0); 
}

inline void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dots = solve2(x1, x2, y1, y2);
    int edges = solve(x1, x2, y1, y2) + solve(y1, y2, x1, x2);
    cout << dots - edges << "\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, tc;
    cin >> n >> m >> tc;
    while (tc--) {
        solve();
    }
}