修墙

GitHub跳转原题关系图返回列表

0 起编号后白格当且仅当 i&j==0,白格构成的四连通图是一棵树;矩形内连通块数等于父亲越出边界的白格数,用数位计数 O(log C) 求出。

OJ: roj

题目 ID: 1780

难度:提高+/省选-

标签:动态规划数位计数位运算python

创建: 2026-10-08 02:13

更新: 2026-10-08 02:13

形式化题目

地图是一个无限大的黑白网格。设第 kk 次迭代后的方块矩阵为 AkA_k:

A0=(W),Ak+1=(AkAkAkBk),A_0 = \begin{pmatrix} W \end{pmatrix}, \qquad A_{k+1} = \begin{pmatrix} A_k & A_k \\ A_k & B_k \end{pmatrix},

其中 BkB_k 是与 AkA_k 同阶的全黑矩阵。无限次迭代后得到整张地图。 把白格看作"用户",两个白格能互相通信当且仅当它们可由四连通的白格路径相连。 给定 qq 个询问,每个询问给出矩形 [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2] (1⩽x1⩽x2⩽1091 \leqslant x_1 \leqslant x_2 \leqslant 10^9,1⩽y1⩽y2⩽1091 \leqslant y_1 \leqslant y_2 \leqslant 10^9), 输出该矩形内白格的连通块(极大的互通用户集合)个数,没有白格时输出 00。

本题的坐标在题面里从 1 开始,下文一律换成 0 起编号,即把输入的四元组各减 1 后 得到闭区间 [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2],且 0⩽x1⩽x2<2300 \leqslant x_1 \leqslant x_2 < 2^{30}。

结论:格子 (i,j)(i, j)(i,ji, j 均 0 起)为白当且仅当 i&⁡j=0i \operatorname{\&} j = 0。

把 i,ji, j 的二进制展开写出来,AkA_k 是 2k×2k2^k \times 2^k 的矩阵,下标恰好用 kk 位表示。 递归式 Ak+1=(AkAkAkBk)A_{k+1} = \begin{pmatrix} A_k & A_k \\ A_k & B_k \end{pmatrix} 的作用是 给下标补上最高位:最高位为 (0,0)(0,0)、(0,1)(0,1)、(1,0)(1,0) 的三块是旧图(最高位不同时为 1), 最高位为 (1,1)(1,1) 的那块全黑。于是"最高位不同时为 1"且"剩余位递归成立", 归纳即得 (i,j)(i, j) 为白   ⟺  i&⁡j=0\iff i \operatorname{\&} j = 0。

i\ji \backslash j 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

读这张 8×88 \times 8 表可以直接观察两件事。第一,白格并不稀少也不连成一片: 第 0 行、第 0 列全是白格,而大的方块黑区把地图切得很碎。 第二,白格之间存在明确的"方向性":每个白格(除 (0,0)(0,0) 外)在行下标减一、 列下标减一这两个方向里恰好有一个方向仍是白格——这正是下一节树结构的来源。

用题面样例的第 1 个询问 [1,5]×[1,5][1,5] \times [1,5](1 起)验算一下:换成 0 起编号是 [0,4]×[0,4][0,4] \times [0,4],逐行数白格得 5+3+3+2+4=175 + 3 + 3 + 2 + 4 = 17 个白格, 其中相邻白格对(水平 88 条 + 竖直 88 条)共 1616 条。 因为白格图是森林(见下文正解第一步),无环,故连通块数 =17−16=1= 17 - 16 = 1,与样例输出一致。 而样例第 4 个询问 [2,2]×[2,2][2,2] \times [2,2](0 起 [1,1]×[1,1][1,1] \times [1,1])里 (1,1)(1,1) 是黑格, 输出 00,提示答案可能为 00,实现时必须保留这一情况。

正解

思路

第一步:找白格图的结构——它是一棵树。 记 lsb(v)\mathrm{lsb}(v) 为 vv 最低位 11 的位置 (规定 lsb(0)=+∞\mathrm{lsb}(0) = +\infty)。因为 i&⁡j=0i \operatorname{\&} j = 0, i,ji, j 中至多只有一个非零,故 (i,j)≠(0,0)(i, j) \neq (0, 0) 时 lsb(i)≠lsb(j)\mathrm{lsb}(i) \neq \mathrm{lsb}(j)。

给每个白格 (i,j)≠(0,0)(i, j) \neq (0, 0) 指定唯一父亲:

父(i,j)={(i−1,j),lsb(i)<lsb(j),(i,j−1),lsb(j)<lsb(i). \text{父}(i, j) = \begin{cases} (i - 1, j), & \mathrm{lsb}(i) < \mathrm{lsb}(j), \\ (i, j - 1), & \mathrm{lsb}(j) < \mathrm{lsb}(i). \end{cases}

设 p=min⁡(lsb(i),lsb(j))p = \min(\mathrm{lsb}(i), \mathrm{lsb}(j)),两种情形分别验算。

情形 lsb(j)<lsb(i)\mathrm{lsb}(j) < \mathrm{lsb}(i)(此时 ii 的第 pp 位为 00,且 ii 的低 pp 位全为 00)。 jj 的第 pp 位为 11、低 pp 位为 00,故 j−1j - 1 的第 pp 位变成 00、低 pp 位变成全 11; 而 ii 在此处全是 00,所以 i&⁡(j−1)=0i \operatorname{\&} (j - 1) = 0,(i,j−1)(i, j-1) 是白格。 另一方面 i−1i - 1 的低 p+1p + 1 位全部变成 11(ii 低 pp 位为 00 且第 pp 位为 00, 借位后第 0∼p0 \sim p 位都置 11),而 jj 的第 pp 位是 11,故 (i−1)&⁡j≠0(i-1) \operatorname{\&} j \neq 0, (i−1,j)(i-1, j) 不是白格。

情形 lsb(i)<lsb(j)\mathrm{lsb}(i) < \mathrm{lsb}(j) 把上面两段的 ii、jj 互换, 同样得到 (i−1,j)(i-1, j) 是白格、(i,j−1)(i, j-1) 不是白格。

也就是说,每个白格(除 (0,0)(0,0) 外)在"行下标减一 / 列下标减一"这两个候选里 恰好有一个是白格,且由 lsb\mathrm{lsb} 的大小唯一决定,父亲因此唯一。

沿父亲往根走,max⁡(lsb(i),lsb(j))\max(\mathrm{lsb}(i), \mathrm{lsb}(j)) 严格下降,不可能成环; (0,0)(0, 0) 是唯一没有父亲的点。所以所有白格连同四邻边构成一棵以 (0,0)(0, 0) 为根的树, 任何矩形诱导出的子图都是森林。

第二步:把它变成"父亲越界"的计数。 森林里每个连通块是一棵树被矩形裁掉一部分, 块内恰好有一个点,其父亲落在矩形外面;反过来说,每个"父亲在矩形外"的白格 也各对应一个不同的连通块(森林中点数 == 边数 ++ 连通块数,逐块数一遍即知)。 于是

答案=#{白格 (i,j)∈R:父(i,j)∉R}+[ (0,0)∈R ]. \text{答案} = \#\{\text{白格 } (i,j) \in R : \text{父}(i,j) \notin R\} + [\,(0,0) \in R\,].

父亲在 R=[x1,x2]×[y1,y2]R = [x_1,x_2] \times [y_1,y_2] 之外只有两种可能:

  • 父亲是 (i−1,j)(i-1, j) 且 i=x1i = x_1(因为 i−1<x1i - 1 < x_1),此时要求 lsb(i)<lsb(j)\mathrm{lsb}(i) < \mathrm{lsb}(j);
  • 父亲是 (i,j−1)(i, j-1) 且 j=y1j = y_1,此时要求 lsb(j)<lsb(i)\mathrm{lsb}(j) < \mathrm{lsb}(i)。

(父亲不可能越过右、下边界,因为父亲的行、列下标都不大于子结点的。)

第三步:把这一维条件写成掩码。对 x1>0x_1 > 0,记 p=lsb(x1)p = \mathrm{lsb}(x_1),则

lsb(x1)<lsb(j)  ⟺  j&⁡(2p+1−1)=0  ⟺  j&⁡Mx=0,Mx=x1∣(2p−1), \mathrm{lsb}(x_1) < \mathrm{lsb}(j) \iff j \operatorname{\&} (2^{p+1} - 1) = 0 \iff j \operatorname{\&} M_x = 0, \qquad M_x = x_1 \mid (2^p - 1),

这两个式子的等价是因为 x1x_1 的第 pp 位为 11,j&⁡x1=0j \operatorname{\&} x_1 = 0 已经强制 jj 的第 pp 位为 00, 于是把"低 pp 位清零"补进掩码正好凑成"低 p+1p+1 位清零"。故

A=#{ j∈[y1,y2]:j&⁡Mx=0 },Mx=x1∣(2lsb(x1)−1), A = \#\{\,j \in [y_1, y_2] : j \operatorname{\&} M_x = 0\,\}, \qquad M_x = x_1 \mid (2^{\mathrm{lsb}(x_1)} - 1),

(x1=0x_1 = 0 时 A=0A = 0;这里 jj 只需满足同余条件,取值仍限制在 [y1,y2][y_1, y_2] 内, 用两个前缀相减得到)。对称地,y1>0y_1 > 0 时把 x,yx, y 互换即得

B=#{ i∈[x1,x2]:i&⁡My=0 },My=y1∣(2lsb(y1)−1). B = \#\{\,i \in [x_1, x_2] : i \operatorname{\&} M_y = 0\,\}, \qquad M_y = y_1 \mid (2^{\mathrm{lsb}(y_1)} - 1).

第四步:数位计数算 #{j⩽X:j&⁡M=0}\#\{j \leqslant X : j \operatorname{\&} M = 0\}。 定义 G(X,M)=#{0⩽j⩽X:j&⁡M=0}G(X, M) = \#\{0 \leqslant j \leqslant X : j \operatorname{\&} M = 0\},X<0X < 0 时 G=0G = 0, 则 A=G(y2,Mx)−G(y1−1,Mx)A = G(y_2, M_x) - G(y_1 - 1, M_x),BB 同理。 从高位到低位扫 XX 的二进制,维护不变量"jj 的高于第 bb 位的部分与 XX 完全相同":

  • 若 XX 的第 bb 位是 11,令 jj 的第 bb 位取 00,则 jj 严格小于 XX, 低位可以任取 MM 为 00 的位,贡献   2 b−popcount⁡(M&⁡(2b−1))\;2^{\,b - \operatorname{popcount}(M \operatorname{\&} (2^b - 1))}; 随后若 MM 的第 bb 位也是 11,jj 无法再取 11 维持前缀相同,直接返回; 否则令 jj 该位取 11(与 XX 相同)继续向下。
  • 若 XX 的第 bb 位是 00,jj 该位只能取 00(才是白格且不超过 XX 前缀),继续。

扫完所有位后补上 j=Xj = X 本身(当 X&⁡M=0X \operatorname{\&} M = 0)。每次 O(log⁡C)O(\log C)。

下表用 X=12=11002X = 12 = 1100_2、M=6=1102M = 6 = 110_2 走一遍流程,应数出 {0,1,8,9}\{0, 1, 8, 9\} 共 44 个。 循环从 (X∣M)=14(X \mid M) = 14 的最高位 b=3b = 3 开始。

位 bb XX 的位 MM 的位 本步动作 累计 GG
3 1 0 j3j_3 取 00;低 3 位里 M=1102M = 110_2 只占 bit 2、bit 1,剩下 bit 0 自由 ⇒23−2=2\Rightarrow 2^{3-2}=2,得 j∈{0,1}j \in \{0, 1\} 2
3 1 0 j3j_3 取 11(与 XX 相同),继续往下 2
2 1 1 j2j_2 取 00:低位里 MM 占 1 个位 ⇒22−1=2\Rightarrow 2^{2-1}=2,得 j∈{8,9}j \in \{8, 9\} 4
2 1 1 MM 该位也是 11,jj 无法再取 11 与 XX 前缀相同,返回 4

扫不到底就返回,所以不再补 j=Xj = X;两个分支 {0,1}\{0,1\} 与 {8,9}\{8,9\} 恰好各自被数了一次, 结果 44 与手算一致。这里的要点是:“令 jj 的第 bb 位取 00”这一支已经把 bb 位以下 所有合法填法一次数完,所以后面只需考虑“jj 与 XX 前缀完全相同”这一支, 每层只有 O(1)O(1) 的开销,整趟扫描 O(log⁡C)O(\log C)。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 次数位计数,每次扫 O(log⁡C)O(\log C)(C⩽109C \leqslant 10^9,约 30 位), 故单次询问 O(log⁡C)O(\log C),总计 O(qlog⁡C)O(q \log C)。 q=106q = 10^6 时 C++ 实测 0.05–0.26 s、Python 实测 1.3–2.2 s(限时 2000 ms,Python 允许超限); 十个数据点在 check_sample.py 下 C++ 全部 PASS、峰值内存 8.3 MB。
  • 空间:只有 O(log⁡C)O(\log C) 的常数表(2 的幂)与 O(q)O(q) 的输出缓冲, 与坐标无关,实测峰值 8.3 MB,远低于 1024 MB。

总结

  • 整道题的枢纽是两个观察:白格判据 i&⁡j=0i \operatorname{\&} j = 0(把迭代式看成"给下标补最高位"), 以及由 lsb\mathrm{lsb} 给出的唯一父亲结构。有了后者,“连通块数"就不必真的搜图, 直接等于"父亲越界的白格数”。
  • "连通块数 == 点数 −- 边数"只在无环时成立,本题先证"白格图是树"再使用; 比它更直接的是父亲计数(连通块数 == 父亲越界的白格数),后者不需要数边, 实现只需两行区间和。
  • 数位计数的掩码 Mx=x1∣(2p−1)M_x = x_1 \mid (2^p - 1) 把"j&⁡x1=0j \operatorname{\&} x_1 = 0 且 lsb(j)>p\mathrm{lsb}(j) > p" 两件事合成一个条件,这是让每次计数只依赖一个整数 MM 的关键;同理 i&⁡My=0i \operatorname{\&} M_y = 0 刻画了竖直方向。
  • 答案可以为 00(矩形内全黑),坐标下界处 x1=0x_1 = 0 或 y1=0y_1 = 0 时对应的 AA、BB 直接为 00,只需单独判 (0,0)(0, 0) 是否在矩形内。

数据来源说明:素材目录里带有 data.py(分层测试数据生成器), 说明 data/ 的 10 个测试点是按题面子任务表自造的,题面本身也是对 GDSOI2018 模拟赛原题的重建,出题意图可能与官方原题存在偏差。 素材的 std.cpp 已用 main.cpp 与真实 data/ 逐点比对(10/10 一致), 且实现思路与题面子任务表(q⩽106q \leqslant 10^6、坐标 ⩽109\leqslant 10^9)相符, 因此本节的正解直接采用 std.cpp 的父亲计数路线。