「杂题记录」Mex

Mex 构造题 (P6852 )

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

分析 Mex 值为 \(v\) 的限制，能够提供两种信息，一种是这段区间中 \(1\)~\(v - 1\) 全部存在，一种是不存在 \(v\)

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

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

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

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