Holes

Link。 暴力做是 \(O(nm)\) 的。怎么优化呢？ 结果用到了一个特别神的东西（罗阿姨认为 useless 的东西），分块。想到这个就豁然开朗了！ 假设块长为 \(\sqrt{n}\)，我们分成若干段，如果 \(i + power_i\) ......

`2023-07-26 16:14:50` [原题](https://www.luogu.com.cn/problem/CF797F) ## 思考 考虑如何暴力转移，观察到老鼠之间的路线如果交叉或者包含都不是最优的，所以我们可以设计状态 $f[i][j]$ 表示把前 $j$ 只老鼠全部放在前 $i$ ......

## Description 有一天 Masha 回到家，发现有 $n$ 只老鼠在它公寓的走廊上，她大声呼叫，所以老鼠们都跑进了走廊的洞中。 这个走廊可以用一个数轴来表示，上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$ ，第 $j$ 个洞有一个坐标 $y_j$ ......

建立一个虚拟点 $p$，满足 $p$ 在 LCT 中编号最小。 如果一个点 $i$ 可以弹到点 $j$ 那么 $i$ 到 $j$ 连一条边。 如果一个点 $i$ 可以被弹出那么向 $p$ 连一条边。 然后，直接用 LCT 即可。 $0$ 操作直接修改即可。 $1$ 操作最后落在哪一个洞就是编号区间最 ......