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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

牛牛现在有一个长度为 n 的序列a。现在牛牛有 q 次询问，每次想询问区间 [l,r] 的 mex 是什么。
一个序列的 mex 定义为最小未出现的自然数。

思路

1.用一个vis数组来记录每一个数最后出现的位置
2.每次输入[l,r],从0开始寻找第一个自然数满足最后出现位置在l之前或在r之后即为这个[l,r]区间内的mex数。

代码

#include<iostream>
using namespace std;
int n,q,a[100005],l,r,vis[100005];
int main(){
    ios::sync_with_stdio(false);//让cin,cout与scanf,printf一样的速度
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[a[i]]=i;
    }
    while(q--){
        cin>>l>>r;
        for(int i=0;i<=n;i++){
            if(vis[i]<l||vis[i]>r){
                cout<<i<<endl;
                break;
            }
        }
    }
}