区间MEX

问题描述

给你一个长度为n的数列，元素编号1到n，第i个元素值为Ai。现在有m个形如(L,R)的提问，你需要回答出区间[L,R]的mex值。即求出区间[L,R]中没有出现过的最小的非负整数。

输入格式

第一行，两个整数n和m
第二行，n个空格间隔的整数，表示数列A
接下来m行，每行两个整数L,R,表示一次询问

输出格式

m行，每行一个整数，表示对应询问的答案。

样例输入

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

样例输出

3
0
3
2
4

数据范围

1<=n,m<=200000
0<=Ai<=200000
1<=L<=R<=n

---

题解

两种解法，都是离线方法。
显然可以用莫队。
假设cnt[]已经记录了[l , r]中每种数字出现的次数，mex已经记录了[l , r]的mex值。
若我们想要得到[l+1 ,r]或[l , r-1]的mex值。对于[l+1 , r]，如果Ai 在[l+1 , r]出现过，那么mex不变。反之，mex变为mex 与Ai 的较小值。[l , r-1]同理。
若我们想要得到[l-1 ,r]或[l , r+1]的mex值。对于[l-1 , r]，如果A(l-1) 在[l , r]出现过，那么mex不变。反之，暴力枚举比mex大的数，更新mex。[l , r+1]同理。
对询问排下序就好啦。
如果你喜欢思（zuo）考（si），还可以考虑线段树。
若mex（i）表示[1 , i]的mex 值，显然mex 是单调不下降的。于是我们可以在O（n）的时间复杂度内算出以1为起点到前n 个数的mex 值，作为前缀数组。
对于询问[l , r]，如果我们将前缀数组更改为以l 为起点到前n 个数的mex 值，那么输出mex[r ]即可。
再来考虑少一个数对mex[]数组的影响。我们预处理next[]数组，其中next[i ]表示下一个值与Ai 相同的数的位置。如果少了 Ai，显然在[i+1 , next[i]-1]中都没有Ai。因此在该区间内的mex[]值都变为与Ai 相比的较小值。
我们将询问按左界排序，避免重复计算。因此每个数只会被去掉一次。
区间修改，用线段树。
不过，推荐大家用莫队。在 **OJ上10个测试点莫队只比线段树慢1000ms，但代码长度只有线段树的一半。

---

代码一：莫队分块

（可以用莫队我为什么要用线段树呢？）

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int ch[200005],now=0,n,m,a[200005],ans[200005];
struct dt{
    int x,y,p,bl;
}q[200005];
bool cmp(dt a,dt b)
{return a.bl==b.bl?a.y<b.y:a.bl<b.bl;}
void qu(int x)
{
    int v=a[x];
    ch[v]--;
    if(!ch[v])now=min(now,v);
}
void ad(int x)
{
    int v=a[x];
    ch[v]++;
    while(ch[now])++now;
}
int main()
{
    int i,l=1,r=0,s;
    scanf("%d%d",&n,&m);
    s=int(sqrt(n));
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].x,&q[i].y);
        q[i].p=i,q[i].bl=(q[i].x-1)/s+1;
    }
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        while(r<q[i].y)++r,ad(r);
        while(r>q[i].y)qu(r),--r;
        while(l<q[i].x)qu(l),++l;
        while(l>q[i].x)--l,ad(l);
        ans[q[i].p]=now;
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

代码二：线段树

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int Q=1000000;
struct qdata{
    int x,y,p;
}s[Q/4];
bool cmp(qdata a,qdata b)
{return a.x<b.x;}
int ans[Q/4],tot=1,n,m,ve[Q],ls[Q],rs[Q],lazy[Q],a[Q/4],nn[Q/4],last[Q/4],me[Q/4],maxr=200000;
bool ch[Q/4]={0};
void putdown(int now)
{
    if(!ls[now])ls[now]=++tot,ve[tot]=2*maxr;
    if(!rs[now])rs[now]=++tot,ve[tot]=2*maxr;
    int lls=ls[now],rrs=rs[now];
    ve[lls]=min(ve[lls],ve[now]);
    ve[rrs]=min(ve[rrs],ve[now]);
    lazy[lls]=lazy[rrs]=1;
    lazy[now]=0;
}
void xiu(int now,int l,int r,int x,int y,int v)
{
    if(lazy[now])putdown(now);
    if(x<=l&&y>=r)
    {
        ve[now]=min(ve[now],v);
        lazy[now]=1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        if(!ls[now])ls[now]=++tot,ve[tot]=2*maxr;
        xiu(ls[now],l,mid,x,y,v);
    }
    if(y>mid){
        if(!rs[now])rs[now]=++tot,ve[tot]=2*maxr;
        xiu(rs[now],mid+1,r,x,y,v);
    }
}
int gm(int now,int l,int r,int x)
{
    if(lazy[now])putdown(now);
    if(l==r)return min(me[l],ve[now]);
    int mid=(l+r)>>1;
    if(x<=mid){
        if(!ls[now])ls[now]=++tot,ve[tot]=2*maxr;
        return gm(ls[now],l,mid,x);
    }
    if(!rs[now])rs[now]=++tot,ve[tot]=2*maxr;
    return gm(rs[now],mid+1,r,x);
}
int main()
{
    ve[1]=maxr*2;
    int i,cnt=0,t=1;
    scanf("%d%d",&n,&m);
    for(i=0;i<=maxr;i++)
        last[i]=n+1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ch[a[i]]=true;
        while(ch[cnt])++cnt;
        me[i]=cnt;
    }
    for(i=n;i;--i)
    {nn[i]=last[a[i]],last[a[i]]=i;}
    for(i=1;i<=m;i++)
        scanf("%d%d",&s[i].x,&s[i].y),s[i].p=i;
    sort(s+1,s+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        while(t<=m&&s[t].x==i)ans[s[t].p]=gm(1,1,maxr,s[t].y),++t;
        xiu(1,1,maxr,i+1,nn[i]-1,a[i]);
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}