问题描述
给你一个长度为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]);
}