当前位置: 首页 > 工具软件 > Mex > 使用案例 >

区间MEX 线段树维护mex数组

沃宇
2023-12-01

NKOJ 4254 区间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


分析:

由于没有修改操作,可以考虑离线算法。

首先考虑暴力的做法。对于固定的左端点,如何用 O(n) 的方法求出左端点与右端点形成的mex数组的值?用一个mark数组从下到大依次枚举没有出现过的数值即可。考虑到mex数组单调不减均摊时间复杂度 O(n) 。如果询问区间的左端点只有一个,那么就能像这样 O(n) 解决。

然而本题的左端点是任意的。但是根据离线算法的基本操作,我们可以把讨论有序化。不妨将询问按左端点从小到大排序。现在假设我们已经求出了以i为左端点的所有区间的mex值,想要得到以i+1为左端点的所有区间的mex值,考虑两种状态如何转移。

从i到i+1,只有一个不同:那就是有些区间里本来有 Ai 但现在没有了。显然只有这样的区间才会受到一定影响。“这样的区间”是哪些区间呢?在以i+1为左端点的区间中,这样的区间是右端点在下一个 Ai 出现前的区间,用一个链表可以方便地维护。

这些区间会受到怎样的影响?考虑 Ai mexj 的大小关系。如果 mexj Ai 要大,那么把 mexj 更新为 Ai ;否则 Ai 就不会对 mexj 的值产生影响。这样做问题就解决了。处理区间修改问题,使用线段树。


最后总结一下做法:

1预处理:

(1)用 O(n) 将以1为左端点的mex值预处理出来;
(2)预处理出每个数下一次出现的位置;
(3)按区间左端点将询问排序;

2.从1到n由小到大讨论。处理完以i为左端点的询问后,对 mex 数组进行区间修改。


代码:

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXM 200005
#define MAXN 200005
#define MAXT 800005
using namespace std;

int N,M,A[MAXN],mex[MAXN],Ans[MAXM],nex[MAXN],las[MAXN];
bool mark[MAXN];
struct node{int l,r,id;}qry[MAXM];

bool operator<(node x,node y)
{
    return x.l<y.l;
}

int tot,lazy[MAXT],ls[MAXT],rs[MAXT],a[MAXT],b[MAXT],v[MAXT];
//lazy等于-1,说明没有需要下放的操作
void Putdown(int p)
{
    int Ls=ls[p],Rs=rs[p];
    if(~lazy[Ls])lazy[Ls]=min(lazy[p],lazy[Ls]);
    else lazy[Ls]=lazy[p];
    if(~lazy[Rs])lazy[Rs]=min(lazy[p],lazy[Rs]);
    else lazy[Rs]=lazy[p];
    v[Ls]=min(v[Ls],lazy[p]);
    v[Rs]=min(v[Rs],lazy[p]);
    lazy[p]=-1;
}

int Build(int x,int y)
{
    tot++;
    int mid=x+y>>1,p=tot;
    a[p]=x;b[p]=y;
    if(x==y)
    {
        v[p]=mex[x];
        return p;
    }

    ls[p]=Build(x,mid);
    rs[p]=Build(mid+1,y);
    v[p]=min(v[ls[p]],v[rs[p]]);

    return p;
}

void Modify(int p,int l,int r,int k)
{
    if(b[p]<l||a[p]>r)return;
    if(~lazy[p])Putdown(p);
    if(a[p]>=l&&b[p]<=r)
    {
        lazy[p]=k;
        v[p]=min(v[p],k);
        return;
    }

    int mid=a[p]+b[p]>>1;
    Modify(ls[p],l,r,k);
    Modify(rs[p],l,r,k);
}

int GetAns(int p,int k)
{
    if(~lazy[p])Putdown(p);
    if(a[p]==b[p]&&a[p]==k)return v[p];
    int mid=a[p]+b[p]>>1;
    if(k<=mid)return GetAns(ls[p],k);
    return GetAns(rs[p],k);
}

int main()
{
    int i,j=0;

    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)scanf("%d",&A[i]);
    for(i=N;i;i--)
    {
        if(las[A[i]]==0)nex[i]=N+1;
        else nex[i]=las[A[i]];
        las[A[i]]=i;
    }
    for(i=1;i<=M;i++)scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id=i;

    for(i=1;i<=N;i++)
    {
        mark[A[i]]=true;
        for(;;j++)if(!mark[j])break;
        mex[i]=j;
    }

    sort(qry+1,qry+M+1);
    memset(lazy,-1,sizeof(lazy));
    Build(1,N);

    for(i=1,j=1;i<=N&&j<=M;i++)
    {
        while(qry[j].l==i)
        {
            Ans[qry[j].id]=GetAns(1,qry[j].r);
            j++;
        }
        Modify(1,1,nex[i]-1,A[i]);
    }

    for(i=1;i<=M;i++)printf("%d\n",Ans[i]);
}
 类似资料: