0 起编号后白格当且仅当 i&j==0,白格构成的四连通图是一棵树;矩形内连通块数等于父亲越出边界的白格数,用数位计数 O(log C) 求出。
OJ: roj
题目 ID: 1780
难度:提高+/省选-
标签:动态规划数位计数位运算python
创建: 2026-10-08 02:13
更新: 2026-10-08 02:13
形式化题目
地图是一个无限大的黑白网格。设第
其中
本题的坐标在题面里从 1 开始,下文一律换成 0 起编号,即把输入的四元组各减 1 后
得到闭区间
结论:格子
把
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | W | W | W | W | W | W | W | W |
| 1 | W | B | W | B | W | B | W | B |
| 2 | W | W | B | B | W | W | B | B |
| 3 | W | B | B | B | W | B | B | B |
| 4 | W | W | W | W | B | B | B | B |
| 5 | W | B | W | B | B | B | B | B |
| 6 | W | W | B | B | B | B | B | B |
| 7 | W | B | B | B | B | B | B | B |
读这张
用题面样例的第 1 个询问
正解
思路
第一步:找白格图的结构——它是一棵树。 记
给每个白格
设
情形
情形
也就是说,每个白格(除
沿父亲往根走,
第二步:把它变成"父亲越界"的计数。 森林里每个连通块是一棵树被矩形裁掉一部分,
块内恰好有一个点,其父亲落在矩形外面;反过来说,每个"父亲在矩形外"的白格
也各对应一个不同的连通块(森林中点数
父亲在
- 父亲是
且 (因为 ),此时要求 ; - 父亲是
且 ,此时要求 。
(父亲不可能越过右、下边界,因为父亲的行、列下标都不大于子结点的。)
第三步:把这一维条件写成掩码。对
这两个式子的等价是因为
(
第四步:数位计数算
- 若
的第 位是 ,令 的第 位取 ,则 严格小于 , 低位可以任取 为 的位,贡献 ; 随后若 的第 位也是 , 无法再取 维持前缀相同,直接返回; 否则令 该位取 (与 相同)继续向下。 - 若
的第 位是 , 该位只能取 (才是白格且不超过 前缀),继续。
扫完所有位后补上
下表用
| 位 |
本步动作 | 累计 |
||
|---|---|---|---|---|
| 3 | 1 | 0 | 2 | |
| 3 | 1 | 0 | 2 | |
| 2 | 1 | 1 | 4 | |
| 2 | 1 | 1 | 4 |
扫不到底就返回,所以不再补
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:20
# update_at: 2026-10-08 02:20
import sys
# 行列都从 0 编号后,(i, j) 是白格当且仅当 i & j == 0。
# 把每个白格 (i, j) 的父亲定为“低位 1 更靠下的那一维的下标减 1”得到的白邻居
# (lsb(i) < lsb(j) 时父亲是 (i-1, j),反之是 (i, j-1),(0, 0) 是全局树根),
# 于是白格图是一棵树;矩形内的连通块数 = 矩形内“父亲落在矩形外”的白格数。
def count_no_bit(X: int, M: int) -> int:
"""数出满足 0 <= j <= X 且 j & M == 0 的 j 的个数。"""
if X < 0:
return 0
res = 0
# 从高位往低位贴着 X 的前缀走路:X 该位为 1 时让 j 该位取 0,低位在 M 为 0 的位上任取
for b in range((X | M).bit_length() - 1, -1, -1):
if X >> b & 1:
free = b - (M & ((1 << b) - 1)).bit_count() # 本位以下 M 为 0、也就是 j 可以任取的位数
res += 1 << free
if M >> b & 1:
return res # 该位 M 也为 1,j 无法继续与 X 的前缀相同
return res + (1 if X & M == 0 else 0) # 补上 j == X 本身
def bound_mask(v: int) -> int:
"""上界 v 对应的掩码 v | (2^lsb(v) - 1):j 与它按位与为 0 等价于 j & v == 0 且 lsb(j) > lsb(v)。"""
return v | ((1 << (v & -v).bit_length() - 1) - 1)
def block_count(x1: int, y1: int, x2: int, y2: int) -> int:
"""矩形 [x1, x2] × [y1, y2](0 编号,闭区间)内的白格连通块数。"""
ans = 0
if x1 > 0:
# 第 x1 行上父亲 (i-1, j) 越过上边界的白格:要求 j & Mx == 0 即 lsb(j) > lsb(x1)
M = bound_mask(x1)
ans += count_no_bit(y2, M) - count_no_bit(y1 - 1, M)
if y1 > 0:
# 第 y1 列上父亲 (i, j-1) 越过左边界的白格,行列互换同理
M = bound_mask(y1)
ans += count_no_bit(x2, M) - count_no_bit(x1 - 1, M)
return ans + (1 if x1 == 0 and y1 == 0 else 0) # 全局树根 (0, 0) 本身
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
q = next(data, 0)
out: list[str] = []
for _ in range(q):
x1, y1, x2, y2 = next(data) - 1, next(data) - 1, next(data) - 1, next(data) - 1
out.append(str(block_count(x1, y1, x2, y2)))
sys.stdout.write('\n'.join(out) + ('\n' if out else ''))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 1780 修墙
*
* 题意:有一个无限大的黑白矩阵,由 "AA / AB"(B 全黑)反复迭代生成。
* 若把行列都从 0 开始编号,可以证明格子 (i, j) 是白色当且仅当 i & j == 0。
* 白格视为用户,四连通的白格互相可达,每次询问一个矩形,输出矩形内白格的连通块数。
*
* 性质:所有白格(连同四邻边)构成一棵以 (0,0) 为根的树。
* lsb(i) 表示 i 的最低位 1 的位置,规定 lsb(0) = +inf。
* 对白格 (i, j)(i & j == 0,故 i、j 不可能有相同的 lsb,除非都为 0):
* lsb(i) < lsb(j) 时,(i-1, j) 是白格,它是 (i, j) 唯一的“向标号更小方向”的邻居;
* lsb(j) < lsb(i) 时,(i, j-1) 是白格,同理。
* 把前一种情况的 (i-1, j)、后一种情况的 (i, j-1) 定为 (i, j) 的父亲((0,0) 无父亲,为树根)。
* 于是白格图是树,任意矩形诱导出的子图是森林。
*
* 计数方式:森林中每个连通块恰有一个“顶端”点(把树根祖先方向视为块外),
* 所以矩形 R 内的连通块数 = #{白格 v ∈ R : v 的父亲不在 R 中}(树根 (0,0) 只要落在 R 内就算一个)。
* 设矩形为 [x1, x2] × [y1, y2](0 下标):
* A:父亲 (i-1, j) 出界 <=> i == x1 且 lsb(x1) < lsb(j):
* A = #{ j ∈ [y1, y2] : j & Mx == 0 },Mx = x1 | (2^lsb(x1) - 1)(x1 > 0 时;否则 A = 0)
* B:父亲 (i, j-1) 出界 <=> j == y1 且 lsb(y1) < lsb(i):
* B = #{ i ∈ [x1, x2] : i & My == 0 },My = y1 | (2^lsb(y1) - 1)(y1 > 0 时;否则 B = 0)
* 若 (x1, y1) == (0, 0) 还要再加 1(全局树根本身)。
* 其中 #{ j ∈ [0, X] : j & M == 0 } 用数位计数:从高位到低位扫,
* 遇到 X 的位为 1 时,让 j 该位取 0、低位在 M 为 0 的位上自由取,贡献 2^(自由位数);
* 但若该位 M 也为 1,则 j 无法继续与 X 前缀相同,直接结束;否则继续(j 该位取 1)。
* 扫完再补上 j == X 本身。单次 O(log C),每组询问 4 次,$q = 10^6$ 时完全够用。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int TOPBIT = 30; // 坐标 < 2^30
ll pw2[TOPBIT + 2]; // 2 的幂
/* ---------- 快速读入 ---------- */
static char inbuf[1 << 20];
static int inlen = 0, inpos = 0;
inline int nextChar() {
if (inpos == inlen) {
inlen = (int)fread(inbuf, 1, sizeof(inbuf), stdin);
inpos = 0;
if (inlen <= 0) return -1;
}
return inbuf[inpos++];
}
inline ll readInt() {
int c = nextChar();
while (c != -1 && (c < '0' || c > '9')) c = nextChar();
ll v = 0;
while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = nextChar(); }
return v;
}
/* ---------- 快速输出 ---------- */
static char outbuf[1 << 21];
static int outlen = 0;
inline void flushOut() {
if (outlen) { fwrite(outbuf, 1, outlen, stdout); outlen = 0; }
}
inline void putChar(char c) {
if (outlen == (int)sizeof(outbuf)) flushOut();
outbuf[outlen++] = c;
}
inline void writeInt(ll v) {
if (v == 0) { putChar('0'); putChar('\n'); return; }
char tmp[24];
int n = 0;
while (v > 0) { tmp[n++] = (char)('0' + (int)(v % 10)); v /= 10; }
while (n > 0) putChar(tmp[--n]);
putChar('\n');
}
/* ---------- 数位计数 ---------- */
// 求 #{ j : 0 <= j <= X, j & M == 0 };X < 0 时返回 0
ll countNoBit(ll X, ll M) {
if (X < 0) return 0;
ll res = 0;
for (int b = TOPBIT; b >= 0; b--) {
if ((X >> b) & 1LL) {
// j 的第 b 位取 0(严格小于 X),低位只能取 M 为 0 的位
int freeBits = b - __builtin_popcountll(M & (pw2[b] - 1));
res += pw2[freeBits];
if ((M >> b) & 1LL) return res; // 该位 M == 1,j 无法继续等于 X 的前缀
}
// X 该位为 0:j 该位也只能取 0,与 X 相同,继续
}
if ((X & M) == 0) res++; // j == X 本身
return res;
}
int main() {
pw2[0] = 1;
for (int i = 1; i <= TOPBIT + 1; i++) pw2[i] = pw2[i - 1] << 1;
ll q = readInt();
for (ll qi = 0; qi < q; qi++) {
ll x1 = readInt() - 1, y1 = readInt() - 1;
ll x2 = readInt() - 1, y2 = readInt() - 1;
ll ans = 0;
if (x1 > 0) {
// 第 x1 行上父亲越过上边界的白格
int p = __builtin_ctzll(x1);
ll M = x1 | (pw2[p] - 1);
ans += countNoBit(y2, M) - countNoBit(y1 - 1, M);
}
if (y1 > 0) {
// 第 y1 列上父亲越过左边界的白格
int p = __builtin_ctzll(y1);
ll M = y1 | (pw2[p] - 1);
ans += countNoBit(x2, M) - countNoBit(x1 - 1, M);
}
if (x1 == 0 && y1 == 0) ans++; // 全局树根 (0,0)
writeInt(ans);
}
flushOut();
return 0;
}复杂度
- 时间:每个询问 4 次数位计数,每次扫
( ,约 30 位), 故单次询问 ,总计 。 时 C++ 实测 0.05–0.26 s、Python 实测 1.3–2.2 s(限时 2000 ms,Python 允许超限); 十个数据点在 check_sample.py下 C++ 全部 PASS、峰值内存 8.3 MB。 - 空间:只有
的常数表(2 的幂)与 的输出缓冲, 与坐标无关,实测峰值 8.3 MB,远低于 1024 MB。
总结
- 整道题的枢纽是两个观察:白格判据
(把迭代式看成"给下标补最高位"), 以及由 给出的唯一父亲结构。有了后者,“连通块数"就不必真的搜图, 直接等于"父亲越界的白格数”。 - "连通块数
点数 边数"只在无环时成立,本题先证"白格图是树"再使用; 比它更直接的是父亲计数(连通块数 父亲越界的白格数),后者不需要数边, 实现只需两行区间和。 - 数位计数的掩码
把" 且 " 两件事合成一个条件,这是让每次计数只依赖一个整数 的关键;同理 刻画了竖直方向。 - 答案可以为
(矩形内全黑),坐标下界处 或 时对应的 、 直接为 ,只需单独判 是否在矩形内。
数据来源说明:素材目录里带有
data.py(分层测试数据生成器), 说明data/的 10 个测试点是按题面子任务表自造的,题面本身也是对 GDSOI2018 模拟赛原题的重建,出题意图可能与官方原题存在偏差。 素材的std.cpp已用main.cpp与真实data/逐点比对(10/10 一致), 且实现思路与题面子任务表(、坐标 )相符, 因此本节的正解直接采用 std.cpp的父亲计数路线。
经过无限次迭代之后,我们就得到了土地对应的黑白矩阵。
无限大的地图,分析起来过于困难。每次会截出一个子矩阵,他想要知道这个子矩阵中的用户在墙的阻隔下组成了多少个联通块,联通块定义为极大的能够互相通信的用户集合。
由于一次询问不足以分析,需要进行