题目
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
输入格式：
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
输出格式：
一行一个数，表示每个询问的答案。
分析
就是一个朴素的莫队题，虽然这个做法复杂度有问题（雾，但是能水过。注意mex肯定小于等于n，所以大于n的数没有意义，无需考虑。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
inline int read(){
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}
return f*x;
}
struct node{
int l,r,no;
}q[210000];
int belong[210000],L[210000],R[210000],sum,block,a[210000];
inline bool cmp(const node &x,const node &y){
if(belong[x.l]==belong[y.l])return x.r<y.r;
return belong[x.l]<belong[y.l];
}
int used[210000],n,mex,ans[210000],cnt;
inline void add(int x){
if(a[x]>n)return;
used[a[x]]++;
if(a[x]==mex){
for(int i=a[x]+1;i<=n;i++)
if(!used[i]){
mex=i;
break;
}
}
}
inline void del(int x){
if(x>n)return;
used[a[x]]--;
if(used[a[x]]<=0&&a[x]<mex)mex=a[x];
}
int main()
{ int m,i,j,k;
n=read(),m=read();
for(i=1;i<=n;i++)a[i]=read();
for(i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].no=i;
block=sqrt(n);
sum=n%block==0?n/block:n/block+1;
for(i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
for(i=1;i<=sum;i++)
L[i]=R[i-1]+1,R[i]=R[i-1]+block;
R[sum]=n;
sort(q+1,q+m+1,cmp);
int le=1,ri=0;
for(i=1;i<=m;i++){
while(ri<q[i].r){
ri++;
add(ri);
}
while(ri>q[i].r){
del(ri);
ri--;
}
while(le<q[i].l){
del(le);
le++;
}
while(le>q[i].l){
le--;
add(le);
}
ans[q[i].no]=mex;
}
for(i=1;i<=m;i++)printf("%d
",ans[i]);
return 0;
}