洛谷P4137 Rmq Problem / mex 题解

题目链接：P4137 Rmq Problem / mex

题意：

有一个长度为 \(n\) 的数组 \(\{a_1,a_2,\ldots,a_n\}\)。

\(m\) 次询问，每次询问一个区间内最小没有出现过的自然数。

输入格式：

第一行，两个正整数 \(n,m\)。

第二行，\(n\) 个非负整数 \(a_1, a_2, \ldots , a_n\)。

接下来 \(m\) 行，每行两个正整数 \(l,r\)，表示一次询问。

输出格式：

输出 \(m\) 行，每行一个数，依次表示每个询问的答案。

数据范围：

\(1\leq n,m\leq 2\times {10}^5,~1\leq l\leq r\leq n,~0\leq a_i\leq 2\times 10^5\)

线段树上二分经典题，维护区间 \(\mathrm{mex}\) 。

建一棵可持久化权值线段树，然后从左往右扫一遍

每次修改当前权值对应的「最后一次出现的位置」为「当前位置」

查询区间 \([l,r]\) 时，答案就是第 \(r\) 棵线段树上，第一个「最后一次出现的位置」小于 \(l\) 的权值。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define push_up(at) down(sum[at] = sum[ls[at]], sum[rs[at]])
#define N ((int)(4e5+15))
#define M ((int)(5e6+14))

int n,Q,idx,tot,a[N],tmp[N],rt[N],ls[M],rs[M],sum[M];
void insert(int l,int r,int x,int k,int pre,int &at)
{
    at = ++tot; ls[at] = ls[pre]; rs[at] = rs[pre];
    if(l == r) return sum[at] = k, void(0);
    int mid = (l + r) >> 1;
    if(x <= mid) insert(l,mid,x,k,ls[pre],ls[at]);
    else insert(mid+1,r,x,k,rs[pre],rs[at]);
    push_up(at);
}
int query(int l,int r,int x,int at)
{
    if(!x || l == r) return tmp[l];
    int mid = (l + r) >> 1;
    if(sum[ls[at]] >= x) return query(mid+1,r,x,rs[at]);
    else return query(l,mid,x,ls[at]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q; tmp[++idx] = 0;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i]; tmp[++idx] = a[i];
        tmp[++idx] = a[i] + 1;
    } sort(tmp + 1,tmp + 1 + idx);
    idx = unique(tmp + 1, tmp + idx + 1) - tmp - 1;
    for(int i=1; i<=n; i++)
    {
        a[i] = lower_bound(tmp + 1, tmp + 1 + idx, a[i]) - tmp;
        insert(1,idx,a[i],i,rt[i-1],rt[i]);
    }
    for(int l,r; Q--; )
    {
        cin >> l >> r;
        cout << query(1,idx,l,rt[r]) << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/rabbithu/solution-p4137