CF1148H Solution

link

对于区间 mex，若固定一个右端点 \(r\)，左端点 \(l\) 越小 mex 肯定越大。

假设我们维护了右端点为 \(n\)，左端点为 \(i\in[1,n]\) 的区间 mex（设为 \(b_i\))，考虑在序列末尾加入一个数 \(x\):

显然有且仅有原先 \(b_i=x\) 的一段 \(b\) 会被改掉。改成什么呢？大概是这样的，设 \(b_i=x\) 的区间为 \([L,R]\)：

• 找到最小的 \(y\) 满足 \(y\) 在 \([R,n]\) 内没有出现过，即 \(lst_y<R\)，\(lst_y\) 为 \(y\) 的最后一次出现位置。

• 区间 \((lst_y,R]\) 的 \(b\) 改为 \(y\)，同时 \(R\gets lst_y\)。

重复这个过程直到 \(L>R\)。这样就完成了对这一段 \(b\) 的修改。

找 \(y\) 的过程可以利用线段树二分或者其他什么数据结构。

实际上，修改 \(b\) 的次数只有 \(\mathcal O(n)\)。

我们每次本质上是把一种颜色的区间分裂成多种其他颜色的。简单归纳一下就会发现是线性的！

考虑询问。将第 \(i\) 次插入完得到的 \(b\) 称为第 \(i\) 个版本的 \(b\)，那么就是要查询前 \(r\) 个版本中 \(i\ge l\) 的 \(b_i=k\) 的个数。

这类似一个矩形求和，如果允许离线我们可以扫描线处理。但是现在强制在线，考虑主席树：

对于每个 \(k\) 分别维护一颗主席树。这样变成了允许区间修改，求区间历史和。

我们维护一下区间的值的和，以及值乘上其修改时间的和。查询时 upper_bound 找到 \(\le r\) 的最后一个版本，在那个版本对应的根里面查询即可。

复杂度 \(\mathcal O(n \log n)\)。