如题。

同时，#953. 【统一省选2025】追忆 时间限制标的是 6s，但即使单测试点耗时 9s，也能通过（？）

首先考虑直接二分值域然后在每行二分有多少个小于 $lim$ 的位置可以做到 $\Theta(n\log V\log n)$ 次询问。

然后考虑整体二分，假设已知 $[L,R]$ 行的最后一个小于 $lim$ 的位置在 $[l-1,r]$ 中。令 $mid=(l+r)/2$，满足 $a_{i,mid}< lim $ 的行会递归到 $[mid+1,r]$，满足 $a_{i,mid}\ge lim$ 的行会递归到 $[l,mid-1]$。

由于 $a_{i,mid}$ 单调不减，所以可以二分出两类行的分界点。

这样每次 check 的询问次数是 $O(n)$，并且卡不满，因为会怎样递归跟二分的 $lim$ 有关。

虽然直接双指针单次 check 也是 $O(n)$ 的，但这个方法更加容易进行一些常数优化：

• 记忆化：

  记忆下来每列求出过的位置，这样在二分分界点的时候可以缩小二分的区间，这个优化在 $lim$ 接近答案的时候很有用。

  这样询问次数的上界变为了 $\Theta(n\log n)$，因为如果二分到的两个 $lim$ 在所有 $a_{i,j}$ 中的排名相同，那么其实不需要任何额外的询问。

• 剪枝：

  假设最后求出的分界点是 $res$，那么 $[L,res]$ 行的 $[l,mid]$ 位置就一定是 $ < lim$ 的了，且 $[res+1,R]$ 行的 $[mid,r]$ 位置就一定是 $\ge lim$ 的了，所以可以记录已经得到的 $< lim $ 和 $\ge lim$ 位置，如果已经可以判定出结果那就直接退出。

  并且这个优化在 $[l,r]$ 大的时候更有用，所以以 bfs 的顺序去递归效果会更好。

  这个优化在 $lim$ 离答案很远的时候很有用。

但是这样会被 hack，但是整体二分的时候给 $mid$ 随机扰动一下就直接过了。