自动搬运

查看原文

来自洛谷，原作者为

	CuteChat **

搬运于2025-08-24 22:34:46，当前版本为作者最后更新于2025-08-18 16:01:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好想不好写的做法。

题解

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

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

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

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

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

• $i \in [x_1, x_2] \cap \Z$。
• $j \in [y_1, y_2 - 1] \cap \Z$。
• $i \operatorname{and} j = 0, i \operatorname{and}\ (j+1) = 0$。

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

• $dig$ 表示所在位。
• $jw$ 表示进位标记，$1$ 表示目前是在进位，$0$ 表示还没有进位。
• $S$ 表示目前 $i$ 与 $x1,x2$、$j$ 与 $y1,y2-1$ 的大小关系，与常规数位动态规划相同。

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

• $jw=0$：目前没有进位，那么 $j+1$ 与 $j$ 的第 $dig$ 位是相同的，有以下两种转移：
  • 让当前位的下一位开始进位，此时 $j$ 的第 $dig$ 位将一定是 $0$，$j+1$ 的第 $dig$ 位将一定是 $1$，而特别的，$j$ 的后面几位也将全部是 $1$，转移至 $dp(dig-1, S', 1)$。
  • 当前位不进位，正常转移即可
• $jw=1$：目前需要进位，那么 $j$ 的第 $dig$ 位只能是 $1$，$j+1$ 的第 $dig$ 位只能是 $0$，转移至 $dp(dig-1,S'.1)$。

而边界情况，即 $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();
	}
}