拜年【题解】

Aurie · 2025-12-29 13:02:42 · 题解

拜年【题解】

这题正解是线性的，不过考虑到这是一场基础赛和管理员的建议，我们把 \log 做法放过去了。

我们要统计满足条件的 (l,r) 的数量，使得：

• 把所有 a_{i,j}\in[l,r] 的格子变成 1，其余变成 0。
• 在这个二进制网格中，从 (1,1) 到 (2,n) 存在一条只经过 1 的四连通路径。

双指针

可以枚举 r，求对于固定的 r 有多少个 l 满足条件。有一个显然的性质：若 l 满足条件，则 l-1 一定满足条件，因为 l-1 相对于 l，值域增大，为 1 的格子会增多，连通性不减弱。

因此，对于一个固定的 r，如果存在合法的 l，则一定可以找到一个区间 [1,x]，满足当且仅当 l\in[1,x] 时合法。

此时可以尝试维护第一个不合法的 L=x+1。又可以发现，若 r 增加 1，L 是单调不降的，因此如果能够 O(K) 的实现 r 扩展，L 收缩，以及查询 (1,1) 和 (2,n) 是否连通就可以双指针实现 O(nK) 的复杂度。

刻画充要条件

注意到本题只有 2 行，结构非常特殊，可以刻画“是否连通”的充要条件，从而做到线性或近线性。

对于一个固定的 (l,r)，对应的二进制网格为 b。

我们关心的是：在 2\times n 的网格上，什么时候 (1,1) 可以到达 (2,n)。

可以证明，其连通当且仅当同时满足：

1. 起点与终点是 1。

   即：

2. 每一列至少有一个 1。

   如果没有，路径被直接切断。

3. 不存在“交叉阻断”结构。

   “交叉阻断”就是说，存在相邻两列：

   • 两列都恰好只有一个 1。
   • 且这两个 1 在不同的行。

   形如：

   1 0    0 1
   0 1    1 0

   这种结构会把路径“剪断”，形成左右不连通的两个块。

代码中的变量含义是：

路径存在等价于：

flag == 2 && cmk == n && cnt == 0

复杂度