P15652题解

yh2023zlh · 2026-03-08 18:08:41 · 题解

省选唯一的签到题。

对于一个排列的区间的 mex，其实等同于这个区间的补集的最小值。（不考虑 l=1,r=n 的情况）

证明：一个数没有在 [l,r] 内出现，但 0 到 n-1 均在序列里出现，所有这个数在区间补集里出现。既然是最小的未出现的数，那定然就是补集的最小值了。

于是我们考虑询问 n 个前缀最小值与 n 个后缀最小值，这样我们发现其实其他所有的询问得到的信息都可以由这 2n 个信息得到：取左端点的前缀最大与右端点的后缀最大，由 min 运算的合并律直接合并即可。

换句话说，我们只要保证序列的前缀最小与后缀最小值正确即可。这是个经典问题，考虑寻找那些最小值与上一个位置不同的点，这些位置的数一定是该最小值。其他的位置上的数，都需要大于上一个位置的最小值（不然在这里就会突变），按照朴素贪心的策略把限制排序然后一个个填数即可。