网格行走 Path
题面
有一个 $n \times m$ 的网格 , 第 $i$ 行第 $j$ 列写有一个数 $a_{i,j}$ ( 从 0 开始 ) , 每个数仅出现一次 .
一条行走路径的价值为所有经过的点的集合的 $\operatorname{mex}$ 的值 .
定义一个集合的 $\operatorname{mex}$ 的值为最小的没有在集合中出现的非负整数 .
解题思路
要想 $\operatorname{mex}$ 的值大于等于 $d$ , 那么需要经过 $0 \ldots d$ 的所有点 .
非法方案是需要两个点即可 : $x_1 < x_2$ , $y_1 > y_2$ . 对于任意一个的点来说 , 在以它为原点的第 1 象限和第 3 象限的点都是非法的 . 数据结构判断 :
- Method 1 : 二分答案 $d$ , 将对应点排序 , 以 $x$ 为第一关键字 , $y$ 为第二关键字 , 相邻点满足 $x$ , $y$ 均不降即可 ( 不需要真正的排序 ) . 复杂度 $O(nm \log nm)$ .
- Method 2 : 动态加点判断 , 复杂度 $O(nm \log n)$ . ( 目前不会 ＞﹏＜