牛牛的mex【思维】

题意

一个长度为 (n) 的序列：(a_1,a_2, dots ,a_n)，现在有 (q) 次询问，每次想询问区间 ([l,r]) 的 (mex) 值。

(n,qleq 10^5,0leq a_i <n,且 a_i 互不相同)

题目链接：https://ac.nowcoder.com/acm/contest/7079/A

分析

从区间外考虑，维护序列的前缀和后缀最小值，不在 ([l,r]) 的最小自然数必定为二者中的最小值。

代码

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int a[N],suf[N],pre[N];
int main()
{
    int n,q,l,r;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    pre[0]=n,suf[n+1]=n;
    for(int i=1;i<=n;i++)
        pre[i]=min(a[i],pre[i-1]);
    for(int i=n;i>=1;i--)
        suf[i]=min(a[i],suf[i+1]);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        printf("%d
",min(pre[l-1],suf[r+1]));
    }
    return 0;
}