纪念碑

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

求网格中最大不含给定建筑的正方形边长,转化为二分答案和扫描线求矩形面积并判定是否盖满可行域。

OJ: roj

题目 ID: 1752

难度:提高+/省选-

标签:二分线段树扫描线

创建: 2026-10-08 12:43

更新: 2026-10-08 12:43

形式化题目

给定一个 n×mn \times m 的网格(左下角为 (1,1)(1,1),右上角为 (n,m)(n,m)),网格中有 pp 座矩形建筑物。第 ii 座建筑物覆盖了从左下角 (xi,1,yi,1)(x_{i,1}, y_{i,1}) 到右上角 (xi,2,yi,2)(x_{i,2}, y_{i,2}) 的区域。

要求在网格中找到一个边长 LL 最大的正方形(其边界必须与网格平行),使得这个正方形完全在 n×mn \times m 网格内部,且与任何一座建筑物的覆盖区域均没有重叠(即不包含且不相交)。求这个最大边长 LL。如果有多个测试用例,直到文件结束为止。

正解

思路

一个边长为 LL 的正方形完全由其左下角的坐标 (lx,ly)(lx, ly) 唯一确定。如果该正方形完全在 n×mn \times m 网格内部,那么它的左下角必然满足:

1≤lx≤W,1≤ly≤H 1 \le lx \le W, \quad 1 \le ly \le H
其中 W=n−L+1W = n - L + 1,H=m−L+1H = m - L + 1。如果 W<1W < 1 或 H<1H < 1,说明网格连一个边长为 LL 的正方形都放不下。我们把 [1,W]×[1,H][1, W] \times [1, H] 称为可行域。

接下来的核心问题是:每一座建筑物 (x1,y1,x2,y2)(x_1, y_1, x_2, y_2) 会在可行域中“禁掉”哪些左下角? 一个左下角位于 (lx,ly)(lx, ly) 的正方形(其区域为 [lx,lx+L−1]×[ly,ly+L−1][lx, lx+L-1] \times [ly, ly+L-1])与建筑物重叠,当且仅当它们在 xx 方向和 yy 方向均相交。

  • xx 方向相交意味着:[lx,lx+L−1]∩[x1,x2]≠∅  ⟺  lx+L−1≥x1 且 lx≤x2  ⟺  lx∈[x1−L+1,x2][lx, lx+L-1] \cap [x_1, x_2] \neq \emptyset \iff lx+L-1 \ge x_1 \text{ 且 } lx \le x_2 \iff lx \in [x_1 - L + 1, x_2]。
  • 同理,yy 方向相交意味着:ly∈[y1−L+1,y2]ly \in [y_1 - L + 1, y_2]。

因此,建筑物会令所有满足以下条件的 (lx,ly)(lx, ly) 变得非法:

lx∈[max⁡(1,x1−L+1),min⁡(W,x2)],ly∈[max⁡(1,y1−L+1),min⁡(H,y2)] lx \in [\max(1, x_1 - L + 1), \min(W, x_2)], \quad ly \in [\max(1, y_1 - L + 1), \min(H, y_2)]
这就把建筑转化为了可行域内的一系列“禁止矩形”。

原问题“是否存在边长 LL 的合法正方形”就转化为:“这些禁止矩形是否没有盖满整个 W×HW \times H 的可行域”。 若没有盖满,说明存在至少一个合法的左下角 (lx,ly)(lx, ly),可以放下一个边长为 LL 的正方形。

显然,若存在边长为 LL 的合法正方形,则必然存在边长为 L−1L-1 的合法正方形。因为可行性关于 LL 单调,所以可以二分答案 LL。判定问题转化为计算矩形面积并。

求矩形面积并的经典算法是扫描线 + 线段树。 因为我们只需要判定“有没有盖满”,即只需要知道“是否存在未被覆盖的点”。线段树在此处维护的是区间覆盖计数的总被覆盖长度(cov)。

  • 全局根节点(整个 yy 轴区间)的 cov 若严格小于 HH,说明这一条扫描线上有缝隙,直接判定存在合法位置,提前返回 true。
  • 若所有扫描线遍历完,或者覆盖总面积等于 W×HW \times H,说明被盖满了,返回 false。

代码

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-07 21:43
# update_at: 2026-10-08 12:35

import sys

type Rect = tuple[int, int, int, int]  # 一幢建筑 (x1, y1, x2, y2),左下角格与右上角格
type Span = tuple[int, int, int, int]  # 它禁止的左下角区域 (xl, xr, yl, yr),y 用半开区间 [yl, yr)


def build_spans(rects: list[Rect], L: int, W: int, H: int) -> list[Span]:
    """边长 L 的正方形左下角局限在 W×H 内;返回落在该域里、真正挡住位置的禁止区域。

    正方形与建筑在 x 方向相交 ⟺ 左下角 x 落在 [x1-L+1, x2],y 方向同理;
    与可行域求交后为空的对可行域毫无影响,直接丢掉。
    """
    spans = [(max(1, x1 - L + 1), min(W, x2), max(1, y1 - L + 1), min(H + 1, y2 + 1))
             for x1, y1, x2, y2 in rects]
    return [s for s in spans if s[0] <= s[1] and s[2] < s[3]]


def seg_add(l: int, r: int, v: int, cnt: list[int], cov: list[int],
            seglen: list[int], size: int) -> None:
    """单位区间 [l, r) 的覆盖计数加 v(+1 进入 / -1 离开),随后回溯维护 cov。

    迭代式 Klee:先沿两条边界路径打标记,再从边界叶子的父结点各自上行重算到根。
    叶子的孩子恒为 0,且 seglen 越界下标恒为 0,所以不必判叶子。
    """
    left, right = l + size, r + size
    first, last = left >> 1, (right - 1) >> 1
    while left < right:
        if left & 1:
            cnt[left] += v
            cov[left] = seglen[left] if cnt[left] > 0 else cov[left << 1] + cov[left << 1 | 1]
            left += 1
        if right & 1:
            right -= 1
            cnt[right] += v
            cov[right] = seglen[right] if cnt[right] > 0 else cov[right << 1] + cov[right << 1 | 1]
        left >>= 1
        right >>= 1
    for node in (first, last):                      # 两条边界路径的祖先各重算一次
        while node:
            cov[node] = seglen[node] if cnt[node] > 0 else cov[node << 1] + cov[node << 1 | 1]
            node >>= 1


def has_gap(rects: list[Rect], n: int, m: int, L: int) -> bool:
    """边长 L 能否放下:可行域非空且禁止矩形没盖满它(有一列留缝就放得下)。"""
    W, H = n - L + 1, m - L + 1
    if W < 1 or H < 1:                              # 网格里根本排不下 L×L
        return False
    spans = build_spans(rects, L, W, H)
    if not spans:
        return True

    # y 方向坐标压缩:叶子是相邻端点之间的单位区间,共 units 段
    ys = sorted({y for s in spans for y in s[2:]})
    units = len(ys) - 1
    order = {y: i for i, y in enumerate(ys)}
    size = 1
    while size < units:
        size <<= 1
    seglen = [0] * (size << 2)
    seglen[size:size + units] = [ys[i + 1] - ys[i] for i in range(units)]
    for i in range(size - 1, 0, -1):
        seglen[i] = seglen[i << 1] + seglen[i << 1 | 1]
    cnt = [0] * (size << 2)
    cov = [0] * (size << 2)

    adds = sorted((s[0], order[s[2]], order[s[3]]) for s in spans)      # 在 xl 处进入
    rems = sorted((s[1] + 1, order[s[2]], order[s[3]]) for s in spans)  # 在 xr+1 处离开
    total, area, prev = W * H, 0, 1
    ia = ir = 0
    cnt_spans = len(spans)
    while ia < cnt_spans or ir < cnt_spans:
        xa = adds[ia][0] if ia < cnt_spans else W + 1
        xb = rems[ir][0] if ir < cnt_spans else W + 1
        cur = xa if xa < xb else xb
        if cur > prev:                              # 上一段 [prev, cur) 的覆盖已确定
            if cov[1] < H:                          # 有一段整列为空 -> 那里任一点都行
                return True
            area += (cur - prev) * cov[1]
            if area >= total:                       # 可行域已被盖满
                return False
            prev = cur
        while ia < cnt_spans and adds[ia][0] == cur:
            _, yl, yr = adds[ia]
            ia += 1
            seg_add(yl, yr, 1, cnt, cov, seglen, size)
        while ir < cnt_spans and rems[ir][0] == cur:
            _, yl, yr = rems[ir]
            ir += 1
            seg_add(yl, yr, -1, cnt, cov, seglen, size)
    if cov[1] < H:
        return True
    area += (W + 1 - prev) * cov[1]
    return area < total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while True:
        n = next(data, None)
        if n is None:                               # 多组数据读到 EOF
            break
        m, p = next(data), next(data)
        # 题面保证给出左下、右上;沿用 main.cpp 的容错:顺序反了也照样收进矩形
        rects: list[Rect] = []
        for _ in range(p):
            x1, y1, x2, y2 = next(data), next(data), next(data), next(data)
            rects.append((min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)))

        lo, hi, best = 0, min(n, m), 0
        while lo <= hi:                             # 可行性关于 L 单调,可以二分
            mid = (lo + hi) >> 1
            if has_gap(rects, n, m, mid):
                best, lo = mid, mid + 1
            else:
                hi = mid - 1
        out.append(str(best))
    print("\n".join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-07 21:43
 * update_at: 2026-10-07 21:43
 */
// 1752《纪念碑》:二分答案 + 扫描线求矩形面积并
//
// 边长 L 的正方形由它的左下角 (lx,ly) 唯一确定:lx∈[1,W]、ly∈[1,H],
// 其中 W=n-L+1、H=m-L+1(放不下就是不可行)。建筑 (x1,y1,x2,y2) 会挡住所有
// 两个方向都相交的左下角,即矩形 xl∈[max(1,x1-L+1), min(W,x2)]、
// yl∈[max(1,y1-L+1), min(H,y2)]。于是:
//     存在 L×L 的空正方形 <=> 这 p 个「禁止矩形」没有盖满 W×H。
// 可行性关于 L 单调(L 可行则 L-1 可行),所以二分 L,每轮用扫描线求矩形面积并。
//
// 线段树直接建在真实 y 坐标的单位区间上(2^20 > 1e6,无需坐标压缩),
// 采用迭代式 Klee 算法:区间加、维护整棵子树被覆盖的总长度,更新只走两条边界路径。

#include <cstdio>
#include <cstring>
#pragma GCC optimize("O3")   // 本题最坏点要跑 ~1.6e7 次线段树区间加,开 O3 压常数

const int MAXP = 400005;         // p 的上限
const int TREE_SHIFT = 20;       // 叶子数 2^20 = 1048576 > m 的上限 1e6
const int N = 1 << TREE_SHIFT;   // 第 i 个叶子代表 y 的单位区间 [i, i+1)

struct Rect { int x1, y1, x2, y2; };  // 一幢建筑:左下角、右上角
struct Span { int xl, xr, yl, yr; };  // 它禁止的左下角区域,y 方向为半开区间 [yl, yr)

static Rect rect[MAXP];
static Span span[MAXP];
static int usableList[MAXP];          // 禁止区域与可行域相交非空的建筑下标
static int addOrd[MAXP], remOrd[MAXP];// 按 xl / xr 升序的下标,即扫描线的进入/离开顺序
static int bucket[1000005];           // 计数排序的桶,键值域 [1, W]
static int cnt[4 * N];                // 结点被整段覆盖的次数
static int cov[4 * N];                // 结点范围内被覆盖的 y 长度;下标 >= 2N 的恒为 0
static int segLen[2 * N];             // 结点 i 代表的 y 长度(单位个数)

static int n, m, p, W, H, usableCnt;

// 区间 [l, r) 加 v(v = +1 进入、-1 离开)。叶子的孩子恒为 0,所以无需判叶子;
// 两条边界路径合并向上回溯,公其先祖(LCA)以下只各走一次,省掉一半的回溯。
static inline void update(int l, int r, int v) {
    int L = l + N, R = r + N;
    const int lift = L >> 1, rit = (R - 1) >> 1;
    while (L < R) {
        if (L & 1) { cnt[L] += v; cov[L] = cnt[L] > 0 ? segLen[L] : cov[L << 1] + cov[L << 1 | 1]; ++L; }
        if (R & 1) { --R; cnt[R] += v; cov[R] = cnt[R] > 0 ? segLen[R] : cov[R << 1] + cov[R << 1 | 1]; }
        L >>= 1; R >>= 1;
    }
    int a = lift, b = rit;
    while (a != b) {   // 两条路径同深度,必然同时到达 LCA
        cov[a] = cnt[a] > 0 ? segLen[a] : cov[a << 1] + cov[a << 1 | 1];
        cov[b] = cnt[b] > 0 ? segLen[b] : cov[b << 1] + cov[b << 1 | 1];
        a >>= 1; b >>= 1;
    }
    for (; a; a >>= 1) cov[a] = cnt[a] > 0 ? segLen[a] : cov[a << 1] + cov[a << 1 | 1];
}

// 计数排序:把 usableList[0..usableCnt) 按 xl(byLeft 真)或 xr 升序写进 dst
static void countingSort(int *dst, int byLeft) {
    int i, key, pos;
    for (i = 1; i <= W; ++i) bucket[i] = 0;
    for (i = 0; i < usableCnt; ++i) {
        key = byLeft ? span[usableList[i]].xl : span[usableList[i]].xr;
        ++bucket[key];
    }
    pos = 0;
    for (i = 1; i <= W; ++i) {
        int c = bucket[i];
        bucket[i] = pos;
        pos += c;
    }
    for (i = 0; i < usableCnt; ++i) {
        int id = usableList[i];
        key = byLeft ? span[id].xl : span[id].xr;
        dst[bucket[key]++] = id;
    }
}

// 判定:是否存在边长 L 的空正方形(即禁止矩形没盖满可行域)
static bool check(int L) {
    W = n - L + 1;
    H = m - L + 1;
    if (W < 1 || H < 1) return false;   // 网格里根本放不下 L×L
    int i, k;
    usableCnt = 0;
    for (i = 0; i < p; ++i) {
        int xl = rect[i].x1 - L + 1; if (xl < 1) xl = 1;
        int xr = rect[i].x2;         if (xr > W) xr = W;
        int yl = rect[i].y1 - L + 1; if (yl < 1) yl = 1;
        int yr = rect[i].y2 + 1;     if (yr > H + 1) yr = H + 1;
        if (xl > xr || yl >= yr) continue;          // 与可行域不相交,挡不住任何位置
        span[i].xl = xl; span[i].xr = xr; span[i].yl = yl; span[i].yr = yr;
        usableList[usableCnt++] = i;
    }
    if (usableCnt == 0) return true;                // 一个都挡不住
    countingSort(addOrd, 1);
    countingSort(remOrd, 0);

    memset(cnt, 0, sizeof(int) * (2 * N));   // 只有 [1, 2N) 会被写,更高下标恒为 0
    memset(cov, 0, sizeof(int) * (2 * N));
    int ja = 0, jr = 0;
    long long area = 0;
    const long long total = (long long)W * H;
    int prevX = 1;
    while (ja < usableCnt || jr < usableCnt) {
        int xa = ja < usableCnt ? span[addOrd[ja]].xl : W + 1;
        int xb = jr < usableCnt ? span[remOrd[jr]].xr + 1 : W + 1;
        int cur = xa < xb ? xa : xb;
        if (cur > prevX) {
            if (cov[1] < H) return true;      // 这一整段里有一列没被盖满 -> 那里任一点都是空正方形
            area += (long long)(cur - prevX) * cov[1];
            if (area >= total) return false;  // 可行域已被盖满
            prevX = cur;
        }
        while (ja < usableCnt && span[addOrd[ja]].xl == cur) {
            k = addOrd[ja++];
            update(span[k].yl, span[k].yr, 1);
        }
        while (jr < usableCnt && span[remOrd[jr]].xr + 1 == cur) {
            k = remOrd[jr++];
            update(span[k].yl, span[k].yr, -1);
        }
    }
    if (cov[1] < H) return true;
    area += (long long)(W + 1 - prevX) * cov[1];
    return area < total;
}

// ── 读入:把整个 stdin 一次性读进缓冲区再自己解析,省掉 scanf 的开销 ──
static char buf[1 << 25];
static int bufLen, bufPos;

static inline int nextInt() {
    while (bufPos < bufLen && (buf[bufPos] < '0' || buf[bufPos] > '9') && buf[bufPos] != '-') ++bufPos;
    bool neg = false;
    if (bufPos < bufLen && buf[bufPos] == '-') { neg = true; ++bufPos; }
    int x = 0;
    while (bufPos < bufLen && buf[bufPos] >= '0' && buf[bufPos] <= '9') {
        x = x * 10 + (buf[bufPos] - '0');
        ++bufPos;
    }
    return neg ? -x : x;
}

int main() {
    bufLen = (int)fread(buf, 1, sizeof(buf), stdin);
    bufPos = 0;
    for (int i = 1; i < N; ++i) segLen[i] = N >> (31 - __builtin_clz(i));
    for (int i = N; i < 2 * N; ++i) segLen[i] = 1;   // 叶子代表一个单位长度
    while (true) {
        while (bufPos < bufLen && (buf[bufPos] < '0' || buf[bufPos] > '9')) ++bufPos;
        if (bufPos >= bufLen) break;      // 输入读完(跳过尾部空白后无数字)
        n = nextInt(); m = nextInt(); p = nextInt();
        for (int i = 0; i < p; ++i) {
            int a = nextInt(), b = nextInt(), c = nextInt(), d = nextInt();
            if (a > c) { int t = a; a = c; c = t; }   // 容错:题面保证给出左下、右上
            if (b > d) { int t = b; b = d; d = t; }
            rect[i].x1 = a; rect[i].y1 = b; rect[i].x2 = c; rect[i].y2 = d;
        }
        int lo = 0, hi = n < m ? n : m, ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (check(mid)) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

复杂度

  • 时间复杂度: 设坐标范围 N=max⁡(n,m)N = \max(n, m)。 二分答案需要 log⁡(min⁡(n,m))\log(\min(n, m)) 次。每次判定(check),需要对最多 pp 个禁止矩形进行扫描线处理。 C++ 中直接在真实坐标系上建树,线段树叶子达 O(N)O(N),每次扫描线为 O(plog⁡N)O(p \log N)(因为每次只修改 O(log⁡N)O(\log N) 个节点,且使用迭代实现); Python 中做了离散化,坐标集大小 O(p)O(p),扫描线为 O(plog⁡p)O(p \log p)。 单组测试用例的总时间复杂度为 O(plog⁡Nlog⁡(min⁡(n,m)))O(p \log N \log(\min(n, m))) 或 O(plog⁡plog⁡(min⁡(n,m)))O(p \log p \log(\min(n, m)))。
  • 空间复杂度: C++ 的线段树大小取决于坐标范围,使用了 2⌈log⁡2N⌉×4×42^{\lceil\log_2 N\rceil} \times 4 \times 4 字节的数组,属于 O(N)O(N)。 Python 由于离散化,线段树大小为 O(p)O(p)。 此外还需存储 pp 个建筑信息,这部分为 O(p)O(p)。 总空间复杂度 O(N+p)O(N + p)(C++)或 O(p)O(p)(Python)。

总结

  • 转化思想:本题关键在于把“放正方形”转化为“正方形左下角可行域”,从而将建筑抽象成了左下角的“禁止矩形”。即当建筑物坐标为 [x1,x2][x_1, x_2],边长 LL 的正方形只有当其左边界 lx∈[x1−L+1,x2]lx \in [x_1 - L + 1, x_2] 才会与之相交。
  • 单调性与二分:由于较小的正方形更容易找到容身之所(约束更弱),即 LL 可行必定蕴含 L−1L-1 可行,答案满足单调性,所以能在外层二分 LL。
  • 线段树判定:扫描线中,线段树的常规用法是维护“被覆盖的长度和”。在本题中,根节点的覆盖长度(cov[1])能够立即告诉我们当前列是否“盖满”。一旦某时刻 cov[1] < H 且当前列是真实的 xx 坐标区间,就说明出现了空隙,二分判定可以立刻以 True 返回(极大地做了常数剪枝)。
  • 语言开销的极限(TLE 风险):本题极限数据(如 Problem 10 中 n=m=106,p=4×105n=m=10^6, p=4 \times 10^5)非常庞大,且需要进行多轮二分。 C++ 虽然不离散化但利用迭代版 Klee 算法、宏观一维数组直接索引、O3O_3 优化,能够轻松跑过。 但在纯 CPython 中,哪怕用尽了生成器、原生迭代、按位运算、离散化,在极限数据点下也需跑超过 30 秒(时限通常在 1~3 秒)。这是因为底层的循环与函数调用开销积累过多,并非算法劣等,而是语言在这个常数级别的操作密度下达到了瓶颈。遇到同等级别的扫线多组测试题,若无法使用 PyPy,强烈建议转用 C/C++。