题解：P15652 [省选联考 2026] 排列游戏 / perm

kaikatandy · 2026-03-08 16:51:03 · 题解

这个题 *800。

尖塔 2 真好玩，考虑到在一个排列中，[l,r] 的 mex 其实是这个区间补集的最小值，那么一个补集可以拆成前后缀，只需要知道前后缀最小值就行，然后这个可以用 n 次前后缀查询 mex 得到（查询到 0 之后就不查询，左右端点不查询刚好 n 次），然后因为可以根据前后缀最小值变化的位置确定某一些位置值，然后其它的位置的值必须不小于 \max(premin_i,sufmin_i)，扫一遍就行了，我上了个线段树求后继，多了只老哥，糖完了，代码没拿到。考场上玩样例做的，考完了才知道这个转化。