# 讲解稿（第 31 课 · 实验四）

> 这一份是**填好的示例**，对应 `reference/` 里那五份参考解。
> 每一题四段：解决什么问题 / 为什么正确 / 复杂度怎么推 / 多大的规模会淘汰它。

---

## p1 · 舞台高度

### 解决什么问题
给 $n$ 个观众的偏好高度 $a_i$ 与一个名额数 $k$，求最大的舞台高度 $h$，
使 $\sum_i \lfloor a_i / h \rfloor \ge k$。回答的是一个整数 $h$，不是方案。

### 为什么正确
不变式：**`sum(a_i // h)` 随 h 单调不增。** 对同一个 $a_i$，$h$ 变大时
$\lfloor a_i/h \rfloor$ 只会变小或不变，逐项相加也只会变小或不变。

这条单调性推出两件事：一是「能让至少 $k$ 个人看清的 $h$」构成一段从 1 开始的前缀
（可行集合是 $[1, h^*]$ 的形状，不会出现中间可行、两边不可行）；二是二分的写法
必须对：我维护的是**可行区间的右端**，所以 `mid = (lo + hi + 1) // 2`
（取上中位数），检查 `mid` 可行就把 `lo` 提到 `mid`，否则把 `hi` 降到 `mid - 1`。
用下中位数配这套更新会卡在 `lo = mid` 上死循环——这是这一题最常见的错法。

不会漏解：只要 `count(mid) >= k` 就说明 $h^* \ge mid$，把左半段整段丢掉是安全的。
不会多算：`hi` 收缩到 `mid - 1` 是因为 `count(mid) < k`，而 $h > mid$ 时
`count` 只会更小，所以 $mid$ 及以上全部不可行。

### 复杂度怎么推
每层二分的区间长度减半，初值 $h \in [1, \max a_i]$，所以层数是
$\log_2(10^9) \approx 30$。每层扫一遍数组（$O(n)$），中途 `break` 只是常数优化，
不改变上界。总共 $O(n \log V)$，其中 $V$ 是值域上界；另外求 `max(a)` 是 $O(n)$。

### 多大的规模会淘汰它
以 $n = 2 \times 10^5$、$a_i \le 10^9$ 算：$30$ 层 × $2 \times 10^5$ =
**约 600 万次整除**，Python 里实测 **0.22 秒**，1 秒的时限很宽。

淘汰它的规模是 $n$ 再大一个量级：$n = 10^7$ 时同样是 30 层 × 10^7 =
**3 亿次整除**，Python 至少 30 秒，1 秒的时限必挂——那时要换的做法不是
「换个容器」，而是放弃逐项求和（例如按值域分桶预处理 `a_i` 的计数，
把每层检查压到 $O(V \log V)$ 的预处理 + $O(\sqrt{V})$ 的分块求和）。
如果 $a_i$ 的上限从 $10^9$ 抬到 $10^{18}$，二分层数从 30 涨到 60，
耗时直接翻倍——这也是要一起估进去的量。

---

## p2 · 四边形合并

### 解决什么问题
$n$ 堆石子排成一行，每次把**连续三堆**合成一堆，代价是这三堆之和。
求合到只剩一堆的最小总代价；$n$ 为偶数时合不到一堆（每次少两堆），输出 $-1$。

### 为什么正确
不变式：`dp[i][j][l]` 是**把 `a[i..j]` 这一段合到还剩 `l` 堆**的最小代价，
而 `l` 与区间长度同奇偶（每次合并少 2 堆，所以长度的奇偶性决定剩余堆数的奇偶性）。
只保留 $l \in \{1, 2, 3\}$（长度是偶数时只可能是 $\{2\}$）就够，因为超过 3 堆时
「还能再合」这件事可以立刻结算掉，不必留到上一层。

转移按**断点**枚举：任何合法方案的最后一次跨越断点的合并，一定发生在某个断点
$k$ 的两侧，而两侧此前都只在自己那半区间内合过（合并只吃相邻元素）。
所以枚举 $k$、两侧各取自己的最优，再把「两侧合计 $l_1 + l_2$ 堆」按规则结算：

- $l_1 + l_2 \le 3$：已经不能再合，`dp[i][j][l1 + l2] = dp[i][k][l1] + dp[k+1][j][l2]`；
- $l_1 + l_2 > 3$：还能合 `merges = (l1 + l2 - 1) // 2` 次，
  每次付**这一段的和**（合并出来的那一堆就是这一段的和），
  合完剩 `(l1 + l2) - 2 * merges` 堆，即把两边代价再加上 `merges × (这一段的和)`。

为什么代价只能这么记：一次合并吃掉的是一段里**连续的三堆**，所以这段合并的代价
恰好等于这三堆之和；把「这段里的合并」全部结算成「付掉若干个这一段的和」，
和合并的顺序无关——先合哪三堆都一样，最后付出去的都是这些和。
我一开始把这一步写成「把 $l_1 + l_2$ 折到一个可写的位置」而漏掉了 $l = 3$ 要再付一次钱，
拿 Dijkstra 暴力一对拍就露了——**这一步是这道题唯一容易错的地方**。

### 复杂度怎么推
状态数：$O(n^2)$ 个区间 × 每个区间最多 3 个可达的剩余堆数 = $O(n^2)$。
转移：每个区间枚举断点 $O(n)$，每个断点数对 $(l_1, l_2)$ 最多 $3 \times 3 = 9$ 组。
合起来 $O(n^3)$（常数约 $9/6$）。空间 $O(n^2)$（每个区间只留 3 个数）；
前缀和是 $O(n)$。

### 多大的规模会淘汰它
$n = 300$ 时的断点总数是 $n^3/6 \approx 450$ 万，Python 里实测 **1.7 秒**
（这份参考解在 n = 299 的最大测试点上就是这个量级），2 秒的时限刚好卡得住。

淘汰它的规模是 $n = 2000$：断点数涨到 $2000^3/6 \approx 13.3$ 亿，
即使每一步只花 0.1 微秒也要 130 秒以上，一定超时。
换句话说这道解法的分水岭在 $n$ 的**一千上下**：$n \le 400$ 安稳，
$n = 1000$ 已经要 1.6 亿起步（Python 十几秒）、$n = 2000$ 无解。
再往上（$n \ge 10^4$）要换的是 GarsiaWachs 那一类专门算法或者
四边形不等式优化，那不是这场里能写出来的东西。

---

## p3 · 数颜色

### 解决什么问题
一条彩带 $n$ 个格子，每个格子一个颜色编号；$q$ 组询问，每组问区间 $[l, r]$ 里
**出现了多少种不同的颜色**（同一颜色出现多次只算一次）。

### 为什么正确
不变式（这一题的全部内容就是它）：**扫到位置 $r$ 时，树状数组里位置 $p$ 上是 1
当且仅当存在某个颜色，使 $p$ 是它在 $[1, r]$ 里最后一次出现的位置。**

由这个不变式，对任意 $l \le r$：

> 颜色 $c$ 在 $[l, r]$ 里出现过 $\iff$ $c$ 的最后一次出现位置 $p_c$ 满足
> $l \le p_c \le r$。

（$\Rightarrow$：$c$ 在 $[l,r]$ 里出现过，那它的最后一次出现也落在 $[1,r]$ 里、
且不会早于 $l$。$\Leftarrow$：$p_c \in [l, r]$ 说明位置 $p_c$ 上的颜色就是 $c$。）
所以 $[l, r]$ 里有几个位置是 1，就有几种颜色——答案就是树状数组上 $[l, r]$ 的区间和，
即 `prefix(r) - prefix(l - 1)`。

为什么按右端点排序就够：不变式只依赖「扫到 $r$」这一个条件，与 $l$ 无关。
所以把所有询问按右端点分桶，扫到 $i$ 时先把「颜色 $c$ 上一次出现的位置」上的 1
减掉（同一颜色只在最后位置留一个 1，保证不重复计），再在 $i$ 上加 1，
然后回答所有右端点等于 $i$ 的询问——每个询问只被回答一次，且回答它的时候
不变式恰好成立。

### 复杂度怎么推
扫一遍 $n$ 个位置，每个位置做两次树状数组单点修改（$O(\log n)$），
再回答若干询问，每个询问做两次前缀查询（$O(\log n)$）。
总共 $O((n + q) \log n)$，空间是树状数组 $O(n)$ 加询问分桶 $O(q)$。

### 多大的规模会淘汰它
$n = q = 2 \times 10^5$ 时是 $(n + q) \log n \approx 720$ 万次操作，
Python 里实测 **0.67 秒**，2 秒的时限够用。

淘汰的边界在这里：$n = q = 10^6$ 时是 $4000$ 万次操作，Python 要十几秒——
**四百万到六百万这个量级是这套写法的上限**，再大就必须换更省常数的写法
（把树状数组换成一维数组 + 手写循环）。

另外要注意被淘汰的不是这套离线思路，而是**现场数颜色**那一版：
它对每组询问扫一遍区间，是 $O(nq)$，在 $n = q = 3000$ 时已经是 900 万次起步，
到 $n = q = 2 \times 10^5$ 就是 $4 \times 10^{10}$（400 亿）次，
比参考解慢 **5000 倍以上**。顺带一提，$a_i$ 到 $10^9$ 只影响离散化那一步
（把颜色映射成 $1..n$ 的编号），不影响复杂度。

---

## p4 · 最长公共子串

> **这一题我放弃了。** 但讲解稿仍然要写——写清「我为什么不写它」，
> 以及「如果写的话，正确解法要靠什么、什么时候会被淘汰」。
> 能说清这两件事，这道题的时间就没有白花。

### 解决什么问题
给两个字符串 $S$、$T$（各到 $10^5$），求最长的**连续公共段**的长度
（是子串，不是子序列）。

### 为什么正确
我放弃的是**代码**，不是**判断**。判断分两层：

1. **「二维 DP」这条路从读题起就不通。** 子串问题的 DP 状态是
   $(i, j)$ = 「以 $S_i$ 与 $T_j$ 结尾的最长公共后缀」，
   转移 `dp[i][j] = dp[i-1][j-1] + 1 if S[i] == T[j] else 0`。
   这个转移本身是对的（归纳：以两个字符结尾的公共后缀，去掉最后一个字符之后
   仍然是以各自前一个字符结尾的公共后缀），但状态数是 $|S| \times |T|$。
2. **正确解法要靠单调性 + 指纹。** 「存在长度为 $L$ 的公共子串」这件事随 $L$
   单调下降：如果存在长度 $L$ 的公共子串，把它尾巴切掉就是长度 $L-1$ 的公共子串。
   所以可行长度是一段前缀 $[0, Ans]$——可以二分 $L$。
   判定「是否存在长度为 $L$ 的公共子串」时，把 $S$ 里每段的
   $(|S| - L + 1)$ 个长度 $L$ 的子串各压成一个能 $O(1)$ 滚动更新的数
   （多项式哈希，双模数压碰撞），塞进集合，再拿 $T$ 的每一段去查集合。
   判定是 $O(|S| + |T|)$，二层合起来 $O((|S| + |T|) \log \min(|S|, |T|))$。

**为什么最后没写**：这条链有三处独立的坑（哈希的模数与底数、二分的上下界与
`mid` 取法、双哈希比较时的元组构造），任何一处错了都会表现为「样例过、大数据错」，
而排查只能靠对拍。估值 180 分钟里有一半是留给返工的——那时剩余预算 55 分钟，
55 < 180，所以我把它整道放弃，把那 55 分钟投给了 p3。

### 复杂度怎么推
二分层数是 $\log_2 \min(|S|, |T|) \le 17$；每层要做
$|S| + |T|$ 次滚动哈希（每次常数个乘加取模），再各插/查一次集合。
所以是 $O((|S| + |T|) \log \min(|S|, |T|))$，空间 $O(|S|)$（集合里最多放
$|S|$ 个长度为 $L$ 的指纹）。
对照：「二维 DP」是 $O(|S| \times |T|)$ 时间、$O(|S| \times |T|)$ 空间，
后缀数组 / 后缀自动机是 $O(|S| + |T|)$ 但实现长度是我的解法的好几倍。

### 多大的规模会淘汰它
以 $|S| = |T| = 10^5$ 算：$17$ 层 × $2 \times 10^5$ = **约 340 万个指纹**，
Python 里这份参考解实测 **1.5 秒**，2 秒的时限刚好卡住——所以我即使写了，
也很可能因为常数被卡（这也是我选择放弃的另一条理由）。

淘汰的边界：**长度到 $10^6$ 就出局。** 那时是 $20$ 层 × $2 \times 10^6$ =
$4000$ 万个指纹，Python 至少 20 秒，2 秒的时限下必然超时。

真正被「规模」淘汰得最彻底的是那个二维 DP：$N = 10^5$ 时是
$10^{10}$ 个状态——**100 亿个**，一个状态哪怕只占 4 字节也要 40 GB 内存，
连开表这一步都过不去；就算退到 $N = 5000$（题目里连子任务 2 都不到），
也是 2500 万个状态、100 MB，时间和内存一起顶到天花板。
一句话记住这道题的规模感：**$N = 5000$ 的平方就是极限，而题目给的是 $10^5$。**

---

## p5 · 雨天迷宫

### 解决什么问题
$n \times m$ 的网格，四种格子（`.` / `-` / `b` / `#`），只能上下左右走。
走一格的代价有一条例外：**从一格 `-` 走到另一格 `-` 是 0**，其余任何一步都是 1。
求从 $(1,1)$ 到 $(n,m)$ 的最小总代价，走不到输出 $-1$。

### 为什么正确
把每个格子看成点、把「走一格」看成边，边权只有 $0$ 与 $1$ 两种。
不变式：**从双端队列队头取出的点，它的距离已经是最终的最短距离。**
支撑它的是队列的第二个性质：队列里任意两点的距离最多相差 1，且**单调不减**。

为什么单调不减：取队头 $u$（距离 $d$）时，把它走一步能到的点放进队列——
代价 0 的邻点从**队头**进（它的距离也是 $d$，和 $u$ 同一层），
代价 1 的邻点从**队尾**进（距离 $d+1$，正好接在最后）。
这两种插入都不破坏「队内距离单调不减、且相邻只差 0 或 1」这个形状。
归纳下去：出队的距离序列是非降的，所以每点**第一次出队**时拿到的就是最短距离
（这就是 Dijkstra 在边权只有 0/1 时的特例，用双端队列代替了堆）。

为什么不会漏掉 $-1$：如果终点被 `#` 围住，它会一直不在队列里，
扫完整队之后 `dist[n-1][m-1]` 仍然是 $-1$，直接输出它即可。
「起点就是终点」也不需要特判会出错：起点距离是 0，出队时立刻命中终点、返回 0。

### 复杂度怎么推
把每个格子看成点、每条相邻关系看成边：点数 $N = nm$，边数 $O(N)$。
每条边最多让一个点入队一次（`dist` 只在被改进时才写，本写法里每个点最多入队常数次），
每次出队处理 4 个邻居。
所以时间 $O(N)$、空间 $O(N)$（`dist` 是 $n \times m$ 的表）。

### 多大的规模会淘汰它
$N = 600 \times 600 = 36$ 万格，Python 里实测 **0.27 秒**，2 秒的时限很宽。
$1000 \times 1000 = 100$ 万格（题面的子任务 3）约 0.8 秒，仍然过得去。

淘汰的边界：**$2000 \times 2000 = 400$ 万格**时，Python 大约是 3 秒起步，
1 至 2 秒的时限就过不去了；而 $10^7$ 格（约 $3162 \times 3162$）按每格
1 微秒的乐观估计也要 **10 秒**，必须换更省常数的写法
（一维数组代替二维表、手写数组队列代替 `deque`、把方向展开成 4 段复制代码）。

比「规模淘汰」更值得记住的是**复杂度淘汰**：
把每一步都当 1 的普通 BFS，在这道题的 $600 \times 600$ 上会把裂冰连片那一档
全算成 1，答案直接偏大——那组数据里有一段 1198 步的 L 形裂冰走廊，
其中 1197 步是免费的，所以最小代价是 300（走廊两端各付 1）；
**按每步都算 1 就会算成 1198，偏了 3 倍**。
它错在模型，不是错在常数。而「先搜一条路径、再沿途把裂冰打折」
的贪心更糟：它算的是**某一条路**的代价，不是最小代价，规模再小也不对。