题目大意
你需要对每一个长度的区间,求出以他为长度的区间的 \(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\) 的直线,用扫描线维护就行了