区间 mex 的刻画手法

· · 算法·理论

定义 对非负整数序列 a_i,记 [l,r] 的区间 mex 为 \text{mex}(l,r)=\text{mex}(a_l,a_{l+1},\cdots, a_r)。

定理 1 若 a_i 是 0 \sim n-1 的排列,必有 \text{mex}(l,r)=\min\left(\min\limits_{i<l} a_i,\min \limits_{i>r} a_i\right)。

证明 设 U=\{0,1,\cdots,n-1\},显然 \text{mex}(S)=\min(U \setminus S)。对排列 a_1 \sim a_n,必有 \{a_i \mid i \in [l,r]\}=U \setminus \{a_i \mid i \in [1,l)\cup (r,n] \},证毕。

定理表明,排列的区间 mex 等价于前后缀 min 合并。

问题 1 给定长为 n 的序列 a_1 \sim a_n,进行 q 次询问,给定 l,r 查询 \text{mex}(l,r)。P4137。

显然 a_i>n 的位置无意义,下文假定值域为 [0,n+1]。

离线对 r 扫描线,维护 p_x 表示数值 x 最后出现的位置,则 i 不在 [l,r] 中出现,当且仅当 p_x<l。

从而 \text{mex}(l,r)=\min\limits_{p_x<l} x。线段树维护 p 数组,节点上维护区间 \min,查询在线段树上二分即可。

复杂度 O(n \log n)。在线将线段树可持久化,复杂度还是 1log。

:::::info[代码]

const int N = 2e5 + 5;
int n, q, a[N];
// 在线询问,可持久化线段树
int tot, T[N], lc[30*N], rc[30*N], val[30*N];   
#define ls lc[rt]
#define rs rc[rt]
void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
int clone(int rt) {
    int u = ++tot;
    return lc[u] = ls, rc[u] = rs, val[u] = val[rt], u; 
}  
int insert(int x, int c, int l, int r, int rt) {
    int u = clone(rt);
    if (l == r) return val[u] = c, u;
    int mid = (l + r) >> 1;
    if (x <= mid) lc[u] = insert(x, c, l, mid, ls);
    else rc[u] = insert(x, c, mid + 1, r, rs);
    return pushup(u), u; 
}
int ask(int x, int l, int r, int rt) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    return val[ls] < x ? ask(x, l, mid, ls) : ask(x, mid + 1, r, rs);
}

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) T[i] = insert(a[i], i, 0, n+1, T[i-1]);
    for (int l, r; q--; ) {
        cin >> l >> r;
        cout << ask(l, 0, n+1, T[r]) << '\n';
    }
} 

:::::

问题 2 给定长为 n 的序列 a_1 \sim a_n,进行 q 次操作,单点修改或查询 \text{mex}(l,r)。

取数值 x 的相邻出现位置 i,j,则 x 不在 [l,r] 只要 \exist (i,j), i < l \le r < j。

取所有 (i,j) 拍到二维平面,设点 (i,j) 权值为 x,查询对 i<l \land j>r 的 2-side 矩形求 \min。修改只改变 O(1) 个单点,用 set 维护每个 x 的出现位置即可。

使用树状数组套动态开点线段树维护二维平面,复杂度 O(n \log^2 n)。

注意特判 i=0\land j=n+1,维护每个数字的首末出现位置并在线段树上二分即可。

:::::info[代码]

const int N = 5e5 + 5, inf = 1e9;
int n, q, a[N], ls[N];
set<int> pos[N];

struct BIT {
    int tot, lc[80*N], rc[80*N], val[80*N];
    BIT() {val[0] = inf;}
    #define ls lc[rt]
    #define rs rc[rt]
    void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
    int create() {
        int u = ++tot;
        return lc[u] = rc[u] = 0, val[u] = inf, u;
    }
    void update(int y, int v, int l, int r, int& rt) {
        if (!rt) rt = create();
        if (l == r) return val[rt] = v, void();
        int mid = (l + r) >> 1;
        if (y <= mid) update(y, v, l, mid, ls);
        else update(y, v, mid + 1, r, rs);
        pushup(rt);
    }
    int ask(int tl, int tr, int l, int r, int rt) {
        if (!rt) return inf;
        if (tl <= l && r <= tr) return val[rt];
        int mid = (l + r) >> 1, res = inf;
        if (tl <= mid) chkmin(res, ask(tl, tr, l, mid, ls));
        if (tr > mid) chkmin(res, ask(tl, tr, mid + 1, r, rs));
        return res;
    }

    int T[N];
    void modify(int x, int y, int v) {
        for (; x <= n; x += lowbit(x)) update(y, v, 1, n, T[x]);
    }
    int ask(int x, int y) {
        int res = inf;
        for (; x >= 1; x -= lowbit(x)) chkmin(res, ask(y, n, 1, n, T[x]));
        return res;
    }
    #undef ls
    #undef rs
} B;

struct segtree {
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    int mx[4*N], mn[4*N];
    void pushup(int rt) {mx[rt] = max(mx[ls], mx[rs]), mn[rt] = min(mn[ls], mn[rs]);}
    void build(int l = 0, int r = n+1, int rt = 1) {
        if (l == r) return setval(l, rt), void();
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
    }
    void setval(int x, int rt) {
        if (pos[x].size() > 2) mx[rt] = *next(pos[x].begin()), mn[rt] = *next(pos[x].rbegin());
        else mx[rt] = n+1, mn[rt] = 0;
    }
    void update(int x, int l = 0, int r = n+1, int rt = 1) {
        if (l == r) return setval(x, rt), void();
        int mid = (l + r) >> 1;
        if (x <= mid) update(x, l, mid, ls);
        else update(x, mid + 1, r, rs);
        pushup(rt);
    }
    int ask1(int x, int l = 0, int r = n+1, int rt = 1) {
        if (mx[rt] <= x) return inf;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        return mx[ls] > x ? ask1(x, l, mid, ls) : ask1(x, mid + 1, r, rs); 
    }
    int ask2(int x, int l = 0, int r = n+1, int rt = 1) {
        if (mn[rt] >= x) return inf;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        return mn[ls] < x ? ask2(x, l, mid, ls) : ask2(x, mid + 1, r, rs); 
    }
    #undef ls
    #undef rs
} T;

void del(int x, int v) {
    int l = *prev(pos[v].lower_bound(x));
    int r = *pos[v].upper_bound(x);
    if (1 <= l) B.modify(l, x, inf);
    if (r <= n) B.modify(x, r, inf);
    if (1 <= l && r <= n) B.modify(l, r, v);
    pos[v].erase(x), T.update(v);
}
void add(int x, int v) {
    int l = *prev(pos[v].lower_bound(x));
    int r = *pos[v].upper_bound(x);
    if (1 <= l && r <= n) B.modify(l, r, inf);
    if (1 <= l) B.modify(l, x, v);
    if (r <= n) B.modify(x, r, v);
    pos[v].emplace(x), T.update(v);
}

void _main() {
    cin >> n >> q;
    for (int i = 0; i <= n+1; i++) pos[i] = {0, n+1};
    for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].emplace(i);
    T.build();
    for (int i = 1; i <= n; i++) {
        if (ls[a[i]]) B.modify(ls[a[i]], i, a[i]);
        ls[a[i]] = i;
    }
    for (int x, v, l, r; q--; ) {
        char op; cin >> op;
        if (op == '?') {
            cin >> l >> r;
            cout << min({B.ask(l-1, r+1), T.ask1(r), T.ask2(l)}) << '\n';
        } else {
            cin >> x >> v;
            del(x, a[x]), a[x] = v, add(x, v);
        }
    }
} 

:::::

定义 区间 [l,r] 为 极短 mex 区间 当且仅当 \nexists [l',r'] \subset [l,r], \text{mex}(l',r')=\text{mex}(l,r)。

定理 2 极短 mex 区间的数目不超过 3n。

证明 \text{mex}(l,r)=0 的极短区间数显然 \le n。下面说明极短正 mex 区间的数目 \le 2n。

取极短正 mex 区间 [l,r],不妨设 a_l>a_r。可知删去 a_l 和 a_r 对 mex 均有影响,从而有

取固定的 l,不难发现 \text{mex}(l+1,r) 关于 r 单调不降,而 r 使区间 mex 从 a_r 突变到 a_l,故合法的 r 至多一个。

对 a_l<a_r 同理论证。综上,极短正 mex 区间的数目 \le 2n。

问题 3 给定长为 n 的序列 a_1 \sim a_n,求出所有极短 mex 区间。

对 r 扫描线。当 a_r 加入时,我们考察哪些 l 对应的 \text{mex}(l,r) 改变。可以得到下列条件:

设 a_r 在前 r-1 个元素中最后出现的位置为 q_r。则条件一刻画为 l \in (q_r,r]。

条件二表明 0 \sim a_r-1 在 [l,r) 中均出现。转化为 p_x 的语言就是 \forall 0 \le x < a_r, p_x \ge l \implies l \le \min \limits_{x \in [0,a_r)} p_x。联立得到 l 满足

q_r < l \le \min_{x \in [0,a_r)} p_x

对 p 维护权值线段树,扫描到 a_r 时在线段树上查询 l \gets \min\limits_{x \in [0,a_r)} p_x 作为左端点上界,若 l>q_r 则 [l,r] 即为极短 mex 区间。

在线段树上二分求出 \text{mex}(l,r)=y。为了寻找 mex 更大的极短区间,令 l \gets p_y 重复上述过程,直到 l \le q_r 终止。

考虑每次 l \gets p_y 都会得到一个极短 mex 区间。由定理 2,内层循环的总次数 \le 2n,从而总复杂度 O(n \log n)。

注意特判区间 mex 为 0 的情形。

定义 区间 [l,r] 为 极长 mex 区间 当且仅当 \nexists [l',r'] \supset [l,r],\text{mex}(l',r')=\text{mex}(l,r)。

问题 4 给定长为 n 的序列 a_1 \sim a_n,求出所有极长 mex 区间。

使用问题 3 的算法求出所有极短 mex 区间,向两侧找到第一个改变 mex 的位置,得到对应的极长区间。

对 \text{mex}(l,r)=y 的极短区间,只要在 y 的出现位置中二分出两侧最近的出现位置即可。复杂度 O(n \log n)。

设 [l,r] 为极短 mex 区间,[L,R] 为对应的极长 mex 区间,则 l' \in [L,l] \land r' \in [r,R] 的 \text{mex}(l',r') 均为对应的区间 mex。

拍到 l-r 平面,mex 相等的范围是 [L,l] \times [r,R] 的 4-side 矩形,称这组矩形为 mex 矩形。

使用极长—极短 mex 区间构造的 mex 矩形是可重不漏的。为了构造不重不漏的 mex 矩形划分,可以在扫描线中输出

\left(\max(q_r,p_y),l\right] \times [r,R]

原理是将每个 l 分配给区间 mex 最后改变的位置。

特判 \text{mex}(l,r)=0 的极大矩形。我们得到的 O(n) 个 mex 矩形,对所有合法区间对应整点构成不重不漏的划分。配图展示了 a=[0,1,0,2,1,0] 的 mex 矩形划分。

:::::info[代码]

int n, a[N], p[N];
vector<int> pos[N];
struct node {int x1, x2, y1, y2, v;};
vector<node> rec;

struct segtree {
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    int val[4*N];
    void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
    void update(int x, int c, int l = 0, int r = n+1, int rt = 1) {
        if (l == r) return val[rt] = c, void();
        int mid = (l + r) >> 1;
        if (x <= mid) update(x, c, l, mid, ls);
        else update(x, c, mid + 1, r, rs);
        pushup(rt);
    }
    int ask(int tl, int tr, int l = 0, int r = n+1, int rt = 1) {
        if (tl <= l && r <= tr) return val[rt];
        int mid = (l + r) >> 1, res = n+1;
        if (tl <= mid) chkmin(res, ask(tl, tr, l, mid, ls));
        if (tr > mid) chkmin(res, ask(tl, tr, mid + 1, r, rs));
        return res;
    }
    int mex(int c, int l = 0, int r = n+1, int rt = 1) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        return val[ls] < c ? mex(c, l, mid, ls) : mex(c, mid + 1, r, rs);
    }
} T;

void mexrect() {
    for (int i = 0; i <= n+1; i++) pos[i].pb(0);
    for (int i = 1; i <= n; i++) pos[a[i]].pb(i);
    for (int i = 0; i <= n+1; i++) pos[i].pb(n+1);
    for (int r = 1; r <= n; r++) {
        int q = p[a[r]]; p[a[r]] = r;
        T.update(a[r], r);
        int l = a[r] ? T.ask(0, a[r] - 1) : r;
        for (int y; l > q; l = p[y]) {
            y = T.mex(l);
            int R = *upper_bound(all(pos[y]), r) - 1;
            rec.pb(node{max(q, p[y])+1, l, r, R, y});
        }
    }
    // 特判 mex=0 的矩形
    for (int k = 1; k < (int)pos[0].size(); k++) {
        int L = pos[0][k-1] + 1, R = pos[0][k] - 1;
        for (int i = L; i <= R; i++) rec.pb(node{i, i, i, R, 0});
    }
} 

:::::