UVA12192 Grapevine 是一道把二分搜索用到极致的老题，常年出现在 ICPC 训练列表里。题目看起来是个二维区间查询，实际上核心就是两把二分：先用lower_bound在行里定位起点，再在对角线上二分边长。我第一次做这题时被"枚举左上角"这个直觉带偏了，写了一版 O(n·m·min(n,m)) 的暴力，交上去直接吃了个 TLE。后来把"行、列分别非降"这个隐含条件真正用起来，才把每个查询压到 O(n(log m + log n)) 的级别。这篇博客把完整推导、AC 代码、输出格式陷阱和一些调试心得一起写出来，适合刚学完二分模板、想找一道综合题练手的人。
1. 题目到底在问什么：一个正方形子矩阵检索问题
1.1 题目背景与关键约束
Grapevine 的题面讲的是葡萄园里的方格数据，读题的时候可以直接忽略背景，把它抽成一个纯矩阵问题：给你一个 N 行 M 列的整数矩阵，满足每一行从左到右非降、每一列从上到下非降。接着给 Q 次询问，每次给你一个下界 L 和上界 U，要求你输出一个整数 d，表示存在一个 d×d 的正方形子矩阵，里面所有元素都位于闭区间 [L, U] 上，且 d 是所有可能里最大的。如果不存在任何合法正方形，答案就是 0。
这道题最麻烦的地方是 N 和 M 都达到了 500 级别，而 Q 在极限数据下非常大，上万很常见。所以单次询问做到 O(n log m + n log n) 已经算理想，但绝对不能出现 O(n·m) 量级的单次询问成本。题目被收录进 UVA 12192 和 LA 4478，两边 Online Judge 上搜的是同一个题，输出格式也很特别：每组数据的所有查询结束后，要单独输出一行短横线。
先强调一个约束细节：题目保证矩阵的行、列都非降，但并不是严格递增，也就是说相邻元素可以相等。这一点对二分搜索没有本质影响，但会影响你设计检查条件时用<、>还是<=、>=。我们后面用的lower_bound正好匹配"非降"序列的语义，所以不用改任何东西。
1.2 矩阵的有序性决定了"检查子矩阵"可以 O(1) 完成
一开始我的第一反应是：对每个左上角，得把 k×k 区域里所有元素逐个检查一遍，确认它们都在 [L, U] 里。这显然是极度浪费的。矩阵的有序性帮我们省掉了这一步。考虑任意一个以 (i, j) 为左上角、边长为 k 的正方形区域，区域里任意一个格子 (r, c) 都满足 i ≤ r < i+k、j ≤ c < j+k。因为列非降，A[r][c] ≥ A[i][c]；再因为行非降，A[i][c] ≥ A[i][j]。合起来就是 A[r][c] ≥ A[i][j]。
同理可以证明区域里的最大值就在右下角：先利用行非降把 A[r][c] 压到 A[i+k-1][c]，再利用列非降压到 A[i+k-1][j+k-1]，于是所有格子的值都不超过右下角。所以判断一个 k×k 正方形是否全落在区间内，根本不用扫描 k² 个格子，只需要看两个位置：左上角是否 ≥ L、右下角是否 ≤ U。这是整个算法能成立的根本原因，也是"行列单调"这个条件最漂亮的价值所在。
2. 为什么暴力会超时：直觉方案的问题
2.1 最直接的枚举思路
如果你没怎么处理过二维单调矩阵，拿到这题的第一直觉多半是：枚举所有左上角 (i, j)，从 d=1 开始，不断尝试扩大边长。每扩大一次，检查新增的右边一列和下边一行是否都在 [L, U] 内。这样做理论上可行，而且利用了"每次扩边只需检查 O(k) 个新格子"的增量思想。每个左上角都要尝试到 min(N-i, M-j) 左右，整体复杂度大约是 O(N·M·min(N,M)) 再乘上 Q。
我当时甚至觉得 500 很小，Q 就算有 1000 也能勉强跑过去，结果随手构造一组全零矩阵、查询区间又覆盖全矩阵，直接就卡死了。原因很简单：全零矩阵里每个起点都能一直扩到边界，增量和剪枝完全失效，你必须老老实实把所有候选都试一遍。
2.2 复杂度分析与不可行原因
来算一笔账：假设 N=M=500，min(N,M)=500，一个查询在最坏情况下要处理的格子组合数量达到 500 × 500 × 500，也就是 1.25×10^8 级别。如果 Q 是一万，直接到 10^12，这在任何比赛环境里都不可能过。即使加入"一旦当前边长无法扩展就 break"的剪枝，最坏情况下矩阵全为同一个数、查询区间又恰好覆盖整个矩阵，你仍然会把所有左上角的所有可能边长都尝试一遍。这个剪枝对随机数据有效，对出题人构造的极限数据毫无办法。
所以说，暴力方向失败不是代码写得不够快，而是思路本身没有利用矩阵的单调性。一个合格的程序员应该从"有序"两个字里嗅到二分的气息。二维有序矩阵里找东西的经典套路不外乎两个：从右上角走阶梯，或者用lower_bound逐行扫描。这道题属于区间查询，阶梯法不太好直接套，于是我们选择后者。
3. 二分搜索的切入点：三个单调性
3.1 行内 lower_bound 定位起点
对于一次给定的查询 [L, U]，我们要做的是找一个合法的 k×k 正方形。先固定左上角的行 i，问题变成：这一行里哪些列可以作为左上角的列？
因为行内非降，第一个满足 A[i][j] ≥ L 的列就是临界列。从这一列开始往右的元素都不小于 L，所以都满足下界要求；在这一列左边，所有元素都小于 L，绝对不可能作为左上角。用 C++ 里的lower_bound可以一行拿到这个临界列：
int j = lower_bound(a[i].begin(), a[i].end(), L) - a[i].begin();如果 j == M，说明这一行整行都小于 L，没有起点；如果 A[i][j] > U，说明起点自己已经超过 U，边长至少为 1 的正方形也不合法。这两种情况可以直接跳过当前行。
这里先提醒一句：lower_bound找的是第一个不小于目标的位置，恰好匹配 A[i][j] ≥ L 的下界条件。如果误用upper_bound，就会多往右挪一位，跳过真正合适的起点，导致答案在某些边界数据上偏小。这个坑在后面踩坑部分会展开讲。
3.2 为什么同一行只需要尝试最靠左的合法起点
有人会问：固定了行 i，这一行里大于等于 L 的列有一大堆，为什么只试第一个？原因和"右下角必须小于等于 U"有关。同一行里起点列越靠右，正方形每列坐标都加了偏移，右下角 A[i+k-1][j+k-1] 也向右下移动，因为列非降，这个右下角值只会变大。也就是说，从更靠右的起点出发，对应的检查条件更严苛，能容纳的最大边长只会更小。
所以我们只需要保留最靠左的合法列作为候选，右移起点不会带来任何收益。这是一个典型的"极点最优"思想：在单调条件下，极值点往往就是最优搜索起点。想清楚这一点，算法从"每行枚举一列"直接降成了"每行最多试一个起点"。
3.3 对角线单调性与边长二分
固定了左上角 (i, j) 之后，问题变成：找满足右下角 ≤ U 的最大边长 k。边长 k 每增加 1，右下角沿对角线向右下走一格。为什么这条对角线上的值单调？还是靠行列非降：A[i+k][j+k] ≥ A[i+k][j+k-1]（行内非降），同时 A[i+k][j+k-1] ≥ A[i+k-1][j+k-1]（列非降），所以相邻对角线元素单调不减。于是对 k 做二分是完全合法的。
二分区间是 k ∈ [1, min(N-i, M-j)]。我们找的是最大的 k 使得 A[i+k-1][j+k-1] ≤ U。这个条件配合起点列已经满足 A[i][j] ≥ L，再加上 1.2 小节的极值结论，就恰好等价于整个正方形都在 [L, U] 内。如果二分的最终结果是 0，说明这个起点连 1×1 都撑不住，答案就不从这个起点更新。
4. 完整做法与复杂度推导
4.1 算法流程分解
把上面的讨论整理成可执行的流程，每个查询的处理步骤非常清晰：
- 初始化 ans = 0。
- 枚举左上角的行 i，从 0 到 N-1。
- 在第 i 行用
lower_bound找第一个 ≥ L 的列 j。 - 如果 j == M 或者 A[i][j] > U，跳过该行。
- 设 lim = min(N-i, M-j)，如果 lim ≤ ans，跳过该行。
- 在 [1, lim] 上二分边长 k，取满足右下角 ≤ U 的最大值 best。
- 用 best 更新 ans。
- 输出 ans。
第 5 步的剪枝需要解释：lim 是这个起点理论上能达到的最大边长，如果它都不超过当前 ans，即使二分的 best 取到 lim，也不可能让 ans 变大，所以直接跳过。这个剪枝在答案已经很大的时候特别有效，能把平均运行时间拉低一个量级。
4.2 时间复杂度与空间复杂度
每个查询枚举 N 行，每行lower_bound是 O(log M)，二分边长是 O(log min(N-i, M-j))，上界是 O(log min(N, M))。所以单次查询的时间复杂度是 O(N(log M + log min(N,M)))。按 N=M=500 来算，log 部分大约 9 次，单次询问只有 500×18 左右的比较量级，Q=10000 也才一亿次上下，C++ 在常规时间限制内能稳稳跑完。空间复杂度是 O(NM)，就是存矩阵本身。这个复杂度远好于平方级做法，也正是这道题能被放在"二分搜索"专题下的原因。
4.3 剪枝的两个安全写法
剪枝一：lim ≤ ans 时 continue。剪枝二：如果 ans 已经等于 min(N, M)，这是理论极限，直接退出整个查询的循环。第二种剪枝对极限数据也有效：当答案已经顶满，没必要再扫剩余行。
剪枝要注意：不能因为第 i 行被跳过就 break 整个循环。列非降只保证"同一列越往下越大"，但下一行的lower_bound结果可能移到更靠左的列，那里的值反而更小，说不定能给出更大的 d。这个问题在 6.2 里专门讲，是我实际踩过的一个坑。
5. 参考实现（C++）与关键细节
5.1 完整 AC 代码
下面是一份可以直接提交的 C++ 实现，使用 C++17 标准。代码里没有用任何花哨技巧，重点是把二分和边界判断写清楚。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin >> n >> m && (n || m)) { vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> a[i][j]; } } int q; cin >> q; while (q--) { int L, U; cin >> L >> U; int ans = 0; for (int i = 0; i < n; ++i) { // 当前行第一个不小于 L 的列 int j = lower_bound(a[i].begin(), a[i].end(), L) - a[i].begin(); // 整行都小于 L，或者起点自己已经大于 U，都不可能形成合法正方形 if (j == m || a[i][j] > U) { continue; } // 以 (i, j) 为左上角的最大理论边长 int lim = min(n - i, m - j); if (lim <= ans) { continue; } // 二分最大边长 k，检查右下角是否不超过 U int lo = 1, hi = lim, best = 0; while (lo <= hi) { int mid = (lo + hi) >> 1; if (a[i + mid - 1][j + mid - 1] <= U) { best = mid; lo = mid + 1; } else { hi = mid - 1; } } ans = max(ans, best); // 理论最大值已经达到，后续行不可能更优 if (ans == min(n, m)) { break; } } cout << ans << '\n'; } // 每组数据结束后输出短横线分隔 cout << "-\n"; } return 0; }5.2 代码逐段解读
整个主体的循环非常紧凑。lower_bound返回的是迭代器，减去begin()得到列下标。注意a[i][j] > U这个判断一定要放在j == m之后，否则当j == m时会越界访问，造成运行时错误或莫名其妙的结果。
lim = min(n - i, m - j)是当前起点能扩展到的最远边界。这里用n - i而不是n - i + 1，是因为边长 k 的右下角行号是i + k - 1，最大只能到 n-1，所以 k 最大是 n-i。同理列方向最大是 m-j，取两者较小值。
二分模板我习惯写带best的while (lo <= hi)版本，因为它的语义清楚：best始终记录最后一次合法的 mid，即使一次都没成功，best也是 0，不会造成下标问题。mid从 1 开始对应右下角就是起点本身，正好覆盖了 1×1 的情况。
5.3 输出格式细节：不要忘了短横线
UVA 这题的输出格式比较特殊：每个查询输出一行答案，但在一组数据的所有查询结束后，还要单独输出一行-，表示该组结束。多组数据之间用这个短横线隔开。如果没有输出这个横线，会得到 Presentation Error。我的建议是在读完 Q 个查询后统一输出一次，而不是每个查询后都打印。同时读入以n == 0 && m == 0终止，终止前不能有任何多余输出。
6. 实战踩坑与调试记录
6.1 lower_bound 用错方向
我第一次写的时候把lower_bound写成了upper_bound，样例能过，但交上去 WA。原因前面提过：upper_bound(a[i].begin(), a[i].end(), L)返回的是第一个严格大于 L 的位置，会把恰好等于 L 的合法起点漏掉。比如某一行元素是 [10, 10, 10]，L=10，upper_bound直接返回末尾，导致这一行被判定为"没有起点"，正确答案全被吞掉。后来改成lower_bound后才恢复正常。
也有人喜欢写成upper_bound(..., L - 1)来代替lower_bound(..., L)，这在 L 是整数时逻辑上成立，但没必要绕圈子。直接用lower_bound语义最清楚，也最不容易在大小边界上出错。
6.2 当 j 到达 m 时直接跳过还是退出循环
有些选手在这里写成break，理由是"这一行都小于 L，下面的行只会更大，所以更没有希望"。这个推理是错的。列非降只保证同一列越往下越大，可下一行的lower_bound可能落到更靠左的列，那个位置的值反而比上一行临界列的值小。
举个最简单的反例，两行三列的矩阵：
1 2 3 4 5 6查询 L=5。第一行整行都小于 5，lower_bound返回 m，但如果此时直接 break，就会漏掉第二行的 [5] 这个 1×1 合法正方形。正确的做法是continue，继续看下一行。这个坑一旦踩到，随机数据很难发现，因为要构造出"前面整行都小于 L、后面行却有合法起点"才触发。
6.3 二分边长的边界控制
二分边长时，hi 不能随便取，比如不能取min(N, M)再在判断里临时防止越界，这样容易把下标算错。正确做法是hi = min(n - i, m - j)，这样i + mid - 1永远不超过 n-1，j + mid - 1永远不超过 m-1。
还有一个常见的细节：如果二分的lo初始值设成 0，会导致 mid 也可能为 0，访问a[i-1][j-1]直接越界。所以lo必须从 1 开始。如果你更习惯维护"最后一个合法位置"的模板，也可以把lo当成答案、hi当上界，但要注意循环不变量的初始状态。
6.4 多组数据下的初始化问题
这个题是多组数据，每组矩阵都不一样。很多人在外层 while 里忘掉把某些容器清空，但用vector<vector<int>> a(n, vector<int>(m))构造时大小完全由当前 n、m 决定，天然安全。真正容易出问题的是 ans 的初始化：每个查询内部 ans 都重新初始化为 0，这没问题；如果你把 ans 定义在 main 外，又忘了在每组数据前重置，就会把上一组的答案带到下一组，导致答案只增不减。
我的建议是尽量把 ans 定义在 while(Q--) 内部，让它每次查询都从零开始，不给状态污染留机会。
6.5 剪枝写错导致的重复计算
lim ≤ ans 这个剪枝安全的前提是 lim 确实是当前起点可能达到的最大边长。如果不小心把 lim 写成min(n - i + 1, m - j + 1)，剪枝条件会变得过松，导致无效计算，但不会出错；反过来把 lim 写小，就会跳过实际上能更新答案的行，直接 WA。我在代码里给 lim 加了一行注释，就是为了防止自己把上下界搞混。另一个容易写错的地方是把continue和break的位置弄反，这个在上面 6.2 已经说过。
7. 从这道题看一类"有序矩阵 + 区间查询"问题
7.1 可以迁移的同型题目
这个算法背后是"有序矩阵 + 区间询问"的经典套路，同类题里最常见的有：行列非降矩阵里找某个数是否存在、统计某个区间内有多少元素、找第 k 小元素。Grapevine 是其中比较综合的一道，因为它把"二维范围检查"压缩成了"两个端点检查"，又把"枚举左上角"压成了"每行只试一个点"。如果你把"正方形"改成"矩形"，问题复杂度会明显上升，需要额外维护长宽两个维度，但思路仍然是利用行列单调性缩小搜索范围。
7.2 进一步的优化空间
上面的解法已经能稳稳通过原题，但还有优化空间。因为lower_bound返回的列 j 其实随行数递增是单调不增的：设 i2 > i1，列非降使得 A[i2][j1] ≥ A[i1][j1] ≥ L，所以第 i2 行的第一个 ≥ L 列 j2 满足 j2 ≤ j1。利用这个单调性，可以把每行找起点的 O(log M) 变成均摊 O(1)。具体做法是从最后一行开始倒着扫，维护一个只向右移动的指针定位临界列，但每行仍然要做一次边长二分。对 N=M=500 的数据收益不大，代码更容易写错，我建议比赛时优先写简单版本，真的卡常数再考虑。
还有一个离线思路：把所有询问按 L 排序，在扫描矩阵时用数据结构维护每个 U 对应的答案。这个做法的理论复杂度更优，但代码量明显上升，属于"知道有这条路就行"的范畴。
7.3 对算法训练的实际价值
我觉得这题在二分专题里属于值得二刷的题目。它不考模板记忆，考的是你能不能把一个二维范围检查转化为一维有序数组上的二分。把左上角、右下角的极值思想吃透之后，很多二维单调问题都可以用类似手段降维。更重要的是，这题逼着你理解lower_bound的返回语义、边界条件、剪枝条件之间的微妙区别。这些细节在高强度比赛里就是 WA 和 AC 的分界线。
我在实际调试这题时还有一个习惯：先用随机小矩阵和暴力枚举对拍，能在一秒内发现 continue/break 写错、lower_bound 写反这类 bug。如果你也被这道题卡过，不妨把上面的代码自己敲一遍，然后故意改坏几个条件跑对拍，很快就能明白每一步为什么不能省。把"二分的是什么、单调性在哪、边界怎么定"这三问想清楚，比刷十道重复模板题有用得多。
