「杂题记录」Mex

📄 PDF 📝 Source

Mex 构造题 (P6852 )

给出一些限制,需要还原一个排列,限制形如:[L,R][L, R] vv ,表示排列 [L,R][L, R] 的Mex 为 vv。 给出任意一种构造方案. P105|P|\le 10^5 ## 分析

分析 Mex 值为 vv 的限制,能够提供两种信息,一种是这段区间中 11~v1v - 1 全部存在,一种是不存在 vv

考虑一个数字 xx 的存在位置有哪些限制,不难发现,所有 vxv\ge x 的限制都会对这个值得位置产生限制。

其实就是所有 vxv\ge x 的限制的交集。区间并不好维护,区间交要好维护的多。

从下到大确定 xx 的位置,可以发现可选区间单增,可以直接填数,能保证最优。

注意 Mex 的第二条限制,可以考虑用线段树或者 set 维护哪些地方没有被占用。