CF1148H 题解

· · 题解

从套娃过来的。

首先考虑如何方便地描述所有子区间的 \text{mex}。这是一个经典套路，考虑扫描线，扫右端点 R，维护一些极长的段 [l, r] 表示 [l, R], [l + 1, R], \ldots, [r, R] 的 \text{mex} 都是同一个值 x。

加入一个数 x = a_R，就找到 \text{mex} 为 x 的左端点区间 [l, r]，现在以这一段的点为左端点，以 R 右端点的区间 \text{mex} 不再是 x，那么我们考虑分裂这个区间。也就是说不断找到最小的数 y，使得 p_y < r（p_y 为 y 最后一次出现的位置），那么 [p_y + 1, r] 这段的值就是 y。暴力更新直到整段都被分裂完毕。然后再加入 R。

因为一个位置最多被分裂一次，所以总共更新的段数是 O(n) 的。

由上面那个做法我们可以发现一个数 x 的贡献是一些左端点在 [l_1, r_1]，右端点在 [l_2, r_2] 的区间，其中 r_2 有可能是当前正在扫的右端点 R，也有可能是这一段已经被删除而导致的。

这是一个类似二维数点的形式。数据结构维护左端点，那么每个位置的贡献是一个与当前正在扫的右端点 R 有关的一次函数形式。因为我们需要查询扫完某个右端点后的答案，所以使用主席树维护，每个值为了快速查主席树的 root 可以开一个 map 或 set。为了方便可以标记永久化。

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

code