[THUPC 2024 初赛] 套娃题解

发布时间 2023-12-21 16:05:20作者: hubingshan

题目大意

你需要对每一个长度的区间,求出以他为长度的区间的 \(mex\) 构成集合的 \(mex\)

\(n\le10^5\)

大致思路

有一个神奇的结论:对于点 \((l,r)\)\(mex_{l,r}\) 的矩形,其中按颜色分割得到的矩形数是 \(O(n)\) 级别的

证明&实现:我们考虑找出这些矩形的过程,可以先求出每个后缀的\(mex\) ,在考虑删点,删点过程是对\(lst_{a_i}\sim i\) 的位置和 \(a_i\)\(min\) ,又由于 \(mex\) 序列是单调不增的,于是最多只会改变一段后缀,前面不会改变,所以每次操作只会新增 \(1\) 个区间,实现同理用\(odt\) 维护即可

于是我们可以先处理出这些矩形,长度为 \(l\) 的区间对应的就是,截距为 \(l\) ,斜率为 \(1\) 的直线,用扫描线维护就行了