区间未出现的最小值（牛客）

链接：https://ac.nowcoder.com/acm/contest/7079/A
来源：牛客网

牛牛现在有一个长度为 n 的序列 a1,a2,…,an​。现在牛牛有 q 次询问，每次想询问区间 [l,r] 的 mex 是什么。

一个序列的 mex 定义为最小未出现的自然数。

输入描述:

第一行两个整数 n,q 表示序列长度和询问次数。

接下来一行 n 个非负整数，表示序列 aia_iai​。

 接下来 q行，每行两个整数 li,ri表示询问的区间。

输出描述:

q 行，每行表示询问的答案。

示例1

输入

复制 5 2 4 3 0 1 2 2 4 1 5

5 2
4 3 0 1 2
2 4
1 5

输出

复制 2 5

2
5

备注:

n,q≤105,0≤ai<nn,q leq 10^5,0 leq a_i < nn,q≤105,0≤ai​<n 且 aia_iai​ 互不相同

区间[l,r]的为左边区间[1,l]的最小值，和区间[r+1,n]的最小值再取一个最小值
所有可以维护正向最小值和反向最小值

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<string> 
#include <math.h> 
#include<memory.h>
#include<cstring>
using namespace std; 
typedef long long ll;
const int maxn=1e6+100;
int pre[maxn];
int prr[maxn];
int a[maxn];
int main(){
    int n,m;
    cin>>n>>m;
    pre[0]=n;
    prr[n+1]=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=min(pre[i-1],a[i]);
    }
    for(int i=n;i>=1;i--){
        prr[i]=min(prr[i+1],a[i]);
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        printf("%d
",min(pre[l-1],prr[r+1])); 
    }
}