求网格中最大不含给定建筑的正方形边长,转化为二分答案和扫描线求矩形面积并判定是否盖满可行域。
OJ: roj
题目 ID: 1752
难度:提高+/省选-
标签:二分线段树扫描线
创建: 2026-10-08 12:43
更新: 2026-10-08 12:43
形式化题目
给定一个
要求在网格中找到一个边长
正解
思路
一个边长为
接下来的核心问题是:每一座建筑物
方向相交意味着: 。 - 同理,
方向相交意味着: 。
因此,建筑物会令所有满足以下条件的
原问题“是否存在边长
显然,若存在边长为
求矩形面积并的经典算法是扫描线 + 线段树。
因为我们只需要判定“有没有盖满”,即只需要知道“是否存在未被覆盖的点”。线段树在此处维护的是区间覆盖计数的总被覆盖长度(cov)。
- 全局根节点(整个
轴区间)的 cov若严格小于,说明这一条扫描线上有缝隙,直接判定存在合法位置,提前返回 true。 - 若所有扫描线遍历完,或者覆盖总面积等于
,说明被盖满了,返回 false。
代码
#!/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()/**
* 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;
}复杂度
- 时间复杂度:
设坐标范围
。 二分答案需要 次。每次判定( check),需要对最多个禁止矩形进行扫描线处理。 C++ 中直接在真实坐标系上建树,线段树叶子达 ,每次扫描线为 (因为每次只修改 个节点,且使用迭代实现); Python 中做了离散化,坐标集大小 ,扫描线为 。 单组测试用例的总时间复杂度为 或 。 - 空间复杂度:
C++ 的线段树大小取决于坐标范围,使用了
字节的数组,属于 。 Python 由于离散化,线段树大小为 。 此外还需存储 个建筑信息,这部分为 。 总空间复杂度 (C++)或 (Python)。
总结
- 转化思想:本题关键在于把“放正方形”转化为“正方形左下角可行域”,从而将建筑抽象成了左下角的“禁止矩形”。即当建筑物坐标为
,边长 的正方形只有当其左边界 才会与之相交。 - 单调性与二分:由于较小的正方形更容易找到容身之所(约束更弱),即
可行必定蕴含 可行,答案满足单调性,所以能在外层二分 。 - 线段树判定:扫描线中,线段树的常规用法是维护“被覆盖的长度和”。在本题中,根节点的覆盖长度(
cov[1])能够立即告诉我们当前列是否“盖满”。一旦某时刻cov[1] < H且当前列是真实的坐标区间,就说明出现了空隙,二分判定可以立刻以 True返回(极大地做了常数剪枝)。 - 语言开销的极限(TLE 风险):本题极限数据(如 Problem 10 中
)非常庞大,且需要进行多轮二分。 C++ 虽然不离散化但利用迭代版 Klee 算法、宏观一维数组直接索引、 优化,能够轻松跑过。 但在纯 CPython 中,哪怕用尽了生成器、原生迭代、按位运算、离散化,在极限数据点下也需跑超过 30 秒(时限通常在 1~3 秒)。这是因为底层的循环与函数调用开销积累过多,并非算法劣等,而是语言在这个常数级别的操作密度下达到了瓶颈。遇到同等级别的扫线多组测试题,若无法使用 PyPy,强烈建议转用 C/C++。