[数据结构与算法]P4137 权值线段树 / 回滚莫队

题意

传送门 P4137 Rmq Problem / mex

题解

权值线段树

将查询离线，按照右界升序排序后依次处理。权值线段树维护每个元素出现的索引最大的位置，特别的，将 $[0,maxn)$ 初始化为 $?1$。那么对于查询 $[l,r)$，答案为索引值小于 $l$ 的最小值。总时间复杂度 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 2E5 + 5, SZ = 1 << 19;
int N, M, A[MAXN], res[MAXN];
struct Query
{
    int l, r, id;
    bool operator<(const Query &o) { return r < o.r; }
} qs[MAXN];
int dat[SZ];

void init(int k = 0, int l = 0, int r = MAXN)
{
    if (r - l == 1)
    {
        dat[k] = -1;
        return;
    }
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    init(chl, l, m), init(chr, m, r);
    dat[k] = min(dat[chl], dat[chr]);
}

void change(int a, int b, int x, int k = 0, int l = 0, int r = MAXN)
{
    if (r <= a || b <= l)
        return;
    if (a <= l && r <= b)
    {
        dat[k] = x;
        return;
    }
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    change(a, b, x, chl, l, m), change(a, b, x, chr, m, r);
    dat[k] = min(dat[chl], dat[chr]);
}

int ask(int x, int k = 0, int l = 0, int r = MAXN)
{
    if (r - l == 1)
        return l;
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    if (dat[chl] < x)
        return ask(x, chl, l, m);
    else
        return ask(x, chr, m, r);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = 0; i < M; ++i)
    {
        auto &q = qs[i];
        cin >> q.l >> q.r;
        --q.l;
        q.id = i;
    }
    sort(qs, qs + M);
    init();
    for (int i = 0, j = 0; i < M; ++i)
    {
        while (j < qs[i].r)
            change(A[j], A[j] + 1, j), ++j;
        res[qs[i].id] = ask(qs[i].l);
    }
    for (int i = 0; i < M; ++i)
        cout << res[i] << '\n';
    return 0;
}

回滚莫队

若已知一个区间的 $mex$，则删除元素后可以 $O(1)$ 地维护这个值。那么使用只删除的回滚莫队即可。总时间复杂度 $O(n\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 2E5 + 5;
int N, M, A[MAXN];
int idx[MAXN], L[MAXN], R[MAXN];
struct Query
{
    int l, r, id;
    bool operator<(const Query &o)
    {
        if (idx[l] != idx[o.l])
            return idx[l] < idx[o.l];
        return r > o.r;
    }
} qs[MAXN];
int cnt[MAXN], _cnt[MAXN], res[MAXN];

void add(int i) { ++cnt[A[i]]; }

void del(int i, int &cur)
{
    if (!--cnt[A[i]])
        cur = min(cur, A[i]);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = 0; i < M; ++i)
    {
        auto &q = qs[i];
        cin >> q.l >> q.r;
        --q.l;
        q.id = i;
    }
    int sz = sqrt(N) + 1;
    for (int l = 0, i = 0; l < N; l += sz, ++i)
    {
        L[i] = l, R[i] = min(l + sz, N);
        for (int j = L[i]; j < R[i]; ++j)
            idx[j] = i;
    }
    sort(qs, qs + M);
    int cur;
    for (int i = 0, l = 0, r = 0, pre = -1; i < M; ++i)
    {
        int ql = qs[i].l, qr = qs[i].r;
        if (idx[ql] == idx[qr - 1])
        {
            for (int j = ql; j < qr; ++j)
                ++_cnt[A[j]];
            int k = 0;
            while (_cnt[k] > 0)
                ++k;
            res[qs[i].id] = k;
            for (int j = ql; j < qr; ++j)
                --_cnt[A[j]];
            continue;
        }

        if (idx[ql] != pre)
        {
            pre = idx[ql];
            int lb = L[idx[ql]], ub = N;
            while (lb < l)
                add(--l);
            while (r < ub)
                add(r++);
            while (l < lb)
                del(l++, cur);
            while (ub < r)
                del(--r, cur);
            int k = 0;
            while (cnt[k] > 0)
                ++k;
            cur = k;
        }

        while (qr < r)
            del(--r, cur);
        int _cur = cur, _l = l;
        while (_l < ql)
            del(_l++, _cur);
        res[qs[i].id] = _cur;
        while (l < _l)
            add(--_l);
    }
    for (int i = 0; i < M; ++i)
        cout << res[i] << '\n';
    return 0;
}