Description

　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

　　第一行n,m。
　　第二行为n个数。
　　从第三行开始，每行一个询问l,r。

Output

　　一行一个数，表示每个询问的答案。

Sample Input

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5

Sample Output

1
2
3
0
3

HINT

数据规模和约定
　　对于100%的数据：
　　1<=n,m<=200000
　　0<=ai<=109
　　1<=l<=r<=n
　　对于30%的数据：
　　1<=n,m<=1000

题目分析

莫队+分块 将颜色分块 维护每个块里颜色出现的种类数 和每种颜色出现的次数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,siz;
int val[200010],sum[200010],num[200010],ans[200010];
struct your
{
    int l,r,id;
}q[200100];
int cmp(your j,your k)
{
    if((j.l-1)/siz==(k.l-1)/siz) return j.r<k.r;
    return (j.l-1)/siz<(k.l-1)/siz;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]),val[i]=(val[i]<=n)?val[i]:n;
    siz=(int)sqrt(1.0*n);  
    for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l>q[i].l) l--,sum[val[l]/siz]+=(num[val[l]]==0),num[val[l]]++;
        while(r<q[i].r) r++,sum[val[r]/siz]+=(num[val[r]]==0),num[val[r]]++;
        while(l<q[i].l) num[val[l]]--,sum[val[l]/siz]-=(num[val[l]]==0),l++;
        while(r>q[i].r) num[val[r]]--,sum[val[r]/siz]-=(num[val[r]]==0),r--;
        int j;
        for(j=0;j*siz+siz-1<=n&&sum[j]==siz;j++);
        for(j=j*siz;num[j]>0;j++);
        ans[q[i].id]=j;
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}