题解：CF1967D Long Way to be Non-decreasing

· · 题解

这题有 *2800？

先把问题转化为一个图论模型：建一张 m 个点的有向图，i 向 b_i 连边。则题目转化为求最小的 k，满足从 a_i 开始走不超过 k 步，走到的点的编号 a'_i 单调不降。

因为每个点的出度都等于 1，所以这张图是根向基环树森林。

二分答案。考虑如何 check。容易想到贪心，令 a_i 走到能走到的不小于 a'_{i - 1} 的最小的点。但是 a'_i 并不好求（不弱于静态二维数点），并且主席树肯定跑不了 10^7，考虑找一些性质。

观察到 \sum (a'_i - a'_{i - 1}) \le m，所以只需 O(m) 次判断 u \rightsquigarrow v 的路径长度是否不超过 k。这是容易的，若 v 是 u 的祖先则路径长度等于 dep_u - dep_v，否则若 v 在从 u 出发可达的环上则路径长度等于 dep_u + 环上距离。简单预处理即可。

时间复杂度 O((m + n) \log m)。

提交记录