区间 mex 学习笔记

· · 题解

Part1 前言

首先，回滚莫队解决区间 mex 是平凡且不提倡的，我曾因为只会回滚莫队而导致在考试时看到一道严格强于区间 mex 且要求 O(n\log n) 时间的题目一头雾水。

区间 mex 的优秀做法更多凭借了 mex 的优秀性质，不仅是单调性。

以下所有颜色均指代 mex 的值。

Part2 从简单模板说起

P4137 是回滚莫队求区间 mex 的模板。

我们考虑将询问离线下来，按右端点从左往右扫描，使用一棵权值线段树维护最后一次出现位置。

每加入一个数 a_r=x 就将权值线段树上的 x 的值赋为 r，并维护区间最小值。

每次询问可以线段树上二分找到一个最大的前缀使得最小值大于等于 l，将其加一就是答案。

如果要求在线也是平凡的，使用可持久化权值线段树即可。

Part3 基于性质的扩展

上面的方法是不够优秀的，因为它并没有办法将 mex 的值表示在线段树上，而是每次都需要查询。

我们可以考虑解决以下两个问题：

  1. 求区间所有子区间的 mex 和；
  2. 求区间所有子区间的子区间本质不同 mex 个数的和。

考虑每一次在数组末尾增加一个数 a_r=x，对于所有答案 ans(l,r-1)\leftarrow ans(l,r) 的变化。

如果 ans(l,r-1)\ne x，那么显然有 ans(l,r)=ans(l,r-1)，没有变化。

否则，ans(l,r)>ans(l,r-1)=x，并且不存在任何的 ans(l,r)=x。

我们可以将其看作一个颜色段分裂成了多个颜色段，这样是均摊 O(n) 的。

我们发现 ans(l,r)\ge ans(l+1,r) 总是成立，如果将 ans([L,R],r) 变为 x+k 时，ans(L-1,r)=x+k，那么我们需要将两段合并为一段。

我们可以从 x+1 开始枚举，这样每一次无意义（没有新生成的区间）枚举都会跳过某一个 a_i 且之后不会访问到，所以也是均摊 O(n) 的。

Upd on 2023.8.23：这里直接枚举的复杂度是错的，只是 CF 上没有卡，必须使用线段树上二分才能保证复杂度正确。

于是上面的问题 1 可以归约为区间赋值区间历史和，可以 O((n+q)\log n) 解决。

问题 2 类似，留作思考。

Part4 将本题转换为二维数点

前面部分的实现中，我们需要用一个三元组 [l,r,tag] 表示每一个颜色上一次覆盖的区间和时间，如果当前没有该颜色则 tag=0，所以 tag 也可以起到标志作用。

查询一个颜色最后一次覆盖的贡献是平凡的，每一次颜色存在区间修改需要将上一次的修改保留，删除颜色也是。

我们用四元组 [l,r,d,u] 表示颜色存在的区间和时间，查询区间 [l,r] 的答案就等价于查询矩形 [l,r,l,r] 的覆盖面积。

显然这部分可以用可持久化线段树维护，常数较大。

当然并不难写，但码量还是有点的，不然为什么我是现在的 CF 最短解？

Part5 直接维护矩形的二分做法

我们还可以直接维护矩形，对于一个矩形 [l,r,d,u]，r\le u 总是成立；

如果存在上一个矩形 [l',r',d',u']，那么以下两个条件一定会满足一个：

询问可以看作求矩形 [l,r,l,r] 的覆盖面积。

我们对矩形面积做前缀和，每次二分找到第一个和最后一个相交的矩形，先将答案赋为区间面积和，不过显然会有突出部分，这时之前的结论就派上用场了！

如图，蓝色表示询问矩形，绿色表示左端点超出的部分，红色表示右端点超出的部分。

注意到红色一定只会向上突出，所以我们可以先减去红色向上和绿色向下的突出部分。

然后二分得出最后一个绿色向左突出的矩形，这部分左端点都相等，时间连续，也可以直接求出矩形面积。

所以我们用三次二分得到了答案，总时间复杂度 O(q\log q)，空间 O(q)。

优势在于常数和空间，当然边界情况还是有点多的。

Part6 后记

3500 的 Difficulty 可能主要是没有普及的原因，虽然是别人让我研究但我还是觉得很有意思。

这道题标志着我的数据结构从实现向思维发展。

可能研究的远远不够。