关于基础莫队的运用 洛谷P4137

题目大意：有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
题解：我们可以发现对于一个区间我们很难维护他的所出现过的自然数，这道题目又可以离线，那么我们可爱的莫队算法就可以祭出来了，莫队可以很轻松的解决一段区间里的各个数的个数问题，重点在于高效的维护mex。
根据抄写题解 我们可以发现只有两种情况在移动区间指针时候会影响到mex值。
1、在删除一个数据时这个数据恰好个数为0了，那么直接修改。
2、再加入一个数据时这个数据恰好是上次查询的mex值，那么结果一定大于上次mex，向上查找，然后修改。
除这两种情况其他都不会影响到结果，莫队板子硬上就好。
注：ai<=1e9是来搞笑的，mex值最大也只可能是n，全部改到n+1就好了
总结：最对于区间需要维护多个值的题目，我们可以使用优秀的莫队来优化复杂度。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct Edge{
    int l,r,id;
}q[maxn];
inline int read()
{
    int ret=0;char c=getchar();
    while(c<'0'||c>'9')	c=getchar();
    while(c>='0'&&c<='9')	ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
int n,m,num[maxn],block,ans[maxn],col[maxn],res;
inline bool cmp(Edge a,Edge b)
{return a.l/block==b.l/block?a.r<b.r:a.l/block<b.l/block;}
inline void add(int now)
{
    col[num[now]]++;
    if(num[now]==res)	while(col[res])res++;
}
inline void del(int now)
{
    if(now==0)	return ;
    col[num[now]]--;
    if(!col[num[now]]&&num[now]<res)	res=num[now];
}
int main()
{
    //freopen("1.txt","r",stdin);
    int l=0,r=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++)	num[i]=read(),num[i]>n+1?num[i]=n+1:true;
    for(int i=1;i<=m;i++)	q[i].l=read(),q[i].r=read(),q[i].id=i;
    block=sqrt(n);
    sort(q+1,q+1+m,cmp);
    for(int i=1;i<=m;i++){
        while(r<q[i].r)	r++,add(r);
        while(r>q[i].r)	r--,del(r+1);
        while(l<q[i].l)	l++,del(l-1);
        while(l>q[i].l)	l--,add(l);
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)	printf("%d\n",ans[i]);
    return 0;
}