浅谈「极小 MEX 区间」

· · 算法·理论

引入

# 定义 什么是极小的 $\text{mex}$ 区间？ > 我们称 $\text{mex}(l,r)=x$ 的区间为 $x\text{-mex}$ 区间。 > > 对于一个 $x\text{-mex}$ 区间 $[l,r]$，如果不存在另一个 $x\text{-mex}$ 区间 $[l',r']\subset[l,r]$，则称 $[l,r]$ 为「极小的 $\text{mex}$ 区间」。 事实上，任意数组中，极小的 $\text{mex}$ 区间只有 $\Theta(n)$ 个。具体地，其数量上界为 $2n$。证明不难，重点在于刻画「极小」这一限制。 > 对于一个固定的右端点 $r$，不妨设 $a_l<a_r$。由于该区间一定包含右端点 $a_r$，为了使 $r$ 极小，必有 $mex(l,r)>a_r$。（否则去除 $a_r$ 之后，区间的 $\text{mex}$ 不会改变） > > 因此，左端点的位置只需满足 $mex(l,r)>a_r$ 即为「合法」。注意到 $l$ 需要极大，这样的位置是唯一的。换言之，**若 $a_l<a_r$，则每个右端点 $r$ 最多找到一个左端点 $l$，使得区间 $[l,r]$ 极小。** > > 最后，如果 $a_l>a_r$，钦定左端点固定，分析过程是对称的；$a_l=a_r$ 时显然不合法。 # 前置知识 前置知识：离线求区间 $\text{mex}$。 > 给定一个数组 $a_i$，以及 $q$ 个询问。每个询问输入两个数 $l, r$，输出 $[l,r]$ 的区间 $\text{mex}$。 这个问题有很多做法，在此介绍一个离线扫描线做法。 先把所有询问按右端点排序，然后从左向右扫描线，假设当前扫描到

i，我们回答所有以 i$ 为右端点的询问。

首先，我们需要维护一个 las 数组，表示每种数上一次出现的位置。事实上区间 [j,i] 的 \text{mex} 就是满足 las_x<j 的最小的 x。因此我们开一棵线段树，维护 las 数组的区间最小值，然后在它上面做线段树二分，就可以查出答案了。

例题：P4137 Rmq Problem / mex

算法介绍

现在来讲如何求出所有极小 \text{mex} 区间。

和求区间 \text{mex} 一样，我们考虑离线扫描线。假设当前扫描到 i，我们要找出所有以 i 为右端点的极小 \text{mex} 区间。由于这些区间一定包含 a_i，为了使其极小，它们的 \text{mex} 必须大于 a_i。随着左端点 j 向左移动，区间的 \text{mex} 一定是单调不降的。因此我们的做法是，先找出 \text{mex} 大于 a_i 的最大的 j 作为初值，然后循环地求出区间 [j,i] 的 \text{mex}，并将 j 扩展到这个数上次出现的位置。显然这样找出的 j 都是极大的左端点，并且不会有漏。

此外我们还需考虑 i 是否为极小的右端点。这件事非常容易，记 a_i 在 i 之前出现的最大下标为 k，我们只需保证 j>k 即可。

最后记得特殊处理 \text{mex}=0 的区间。

例题：P13780「o.OI R2」愿天堂没有分块

实现

实现还是有些讲究的。

注意到 las 数组就是线段树的所有叶结点，那么有没有一种线段树可以 \Theta(1) 访问叶结点呢？当然可以，只需使用 zkw 线段树即可。我们上述的所有操作，都只涉及值域线段树上单点修改，因此 zkw 线段树也可以带来显著的常数优化，轻易卡到了 P13780 的最优解。

以防你不知道 zkw 线段树是什么，或者如何在 zkw 线段树上二分，这里提供一篇介绍 zkw 线段树的博客：浅析线段树实现

然后就是完整代码了。

#define ffopen(s) \
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), cerr.tie(0); \
if (*#s) freopen(#s ".in", "r", stdin); \
if (*#s) freopen(#s ".out", "w", stdout); \
//
#include <bits/stdc++.h>
#define chkmax(x, y) ((x)=max((x),(y)))
#define chkmin(x, y) ((x)=min((x),(y)))
using namespace std;
using intl = long long;
using pii = pair<int, int>;
const int N = 500000, inf = 0x3f3f3f3f;

struct Segt {
    int st[N * 3 + 10], tn;
    void build(int n) {
        for (tn = 1; tn <= n + 1; tn <<= 1);
        memset(st, 0, (tn + n + 3) * sizeof(*st));
    }
    void pushup(int u) { if (u) st[u] = min(st[u << 1], st[u << 1 | 1]); }
    void modify(int u, int val) { st[u += tn] = val; do pushup(u >>= 1); while (u); }
    int query(int l, int r) {
        int res = inf;
        for (l += tn, r += tn + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmin(res, st[l++]);
            if (r & 1) chkmin(res, st[--r]);
        } return res;
    }
    int find(int pos) {
        int u = 1;
        while (u < tn) {
            int now = st[u <<= 1];
            if (now >= pos) u ^= 1;
        } return u - tn;
    }
    int operator[] (const int& i) { return st[i + tn]; }
} las;
// zkw 线段树板子，重载了 [] 运算，las[i] 等价于 query(i, i)

int n, a[N + 10];
vector<pii> res[N + 10]; // 求出的极小mex区间

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    las.build(n);
    for (int i = 1; i <= n; i++) {
        int p = las[a[i]]; las.modify(a[i], i);
        if (a[i]) res[0].emplace_back(i, i);
        for (int j = las.query(0, a[i]), mex; j > p; j = las[mex]) {
            mex = las.find(j);
            res[mex].emplace_back(j, i);
        }
    }
    // 输出所有极小 mex 区间
    for (int mex = 0; mex <= n; mex++) {
        for (auto [l, r] : res[mex]) {
            cout << l << ' ' << r << '\n';
        }
        cout << '\n';
    }
    return 0;
}