描述 Description
给定一个长度为 n 的数列 A，数列的第 i 个元素是 Ai （从 1 开始编号）。你需要回答 q 个询问， 每个询问的参数是一个二元组（l ，r） (l ≤ r ，表示查询 mex({Al , Al+1 , … , Ar}) 的值。
所谓 mex ，就是 SG 定理中那个函数，也就是“Minimum Exclusive” 的缩写。对一个非负整数组成的集合 S, mex(S) 的值等于最小的不属于集合 S 的非负整数。
输入格式 InputFormat
输入文件第一行包含 2 个空格隔开的正整数 n 和 q，代表序列 A 的长度和询问个数。
输入文件第二行包含 n 个空格隔开的非负整数，第 i 个数表示 Ai 的值。
接下来 q 行，每行包含 2 个空格隔开的正整数 l 和 r (1 ≤ l ≤ r ≤ n)，表示一个查询的参数。
输出格式 OutputFormat
输出文件应当包含 q 行，每行一个正整数，表示输入文件中对应询问的答案。
样例输入 SampleInput
7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
样例输出 SampleOutput
3
0
3
2
4
数据范围和注释 Hint
第 1 个询问： mex({0,2,l}) = 3.
第 2 个询问： mex({2,l}) = 0.
第 3 个询问： mex({0,2,l,0}) = 3.
第 4 个询问： mex({l,0,l,3}) = 2.
第 5 个询问： mex({2,l,0,l,3,2}) = 4.
来源 Source
这里是题目来源。
代码 Code
线段树。预处理区间 [1,x] 的 mex。每次更新区间内的 mex 的值。询问排序之后离线做。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff
struct tnode
{
int l,r,mex;
};
struct question
{
int l,r,id;
}q[200001];
tnode tree[1000000];
int a[200001],tmex[200001],ans[200001],next[200001],c[200001];
bool b[200001];
int i,j,t,n,m,k,p,z,y,x,last;
void build(int k,int tl,int tr)
{
int i,j,t,mid;
tree[k].l=tl;tree[k].r=tr;tree[k].mex=inf;
if (tl==tr)
{
tree[k].mex=tmex[tl];
return ;
}
mid=(tl+tr)>>1;
build(k<<1,tl,mid);
build(k<<1|1,mid+1,tr);
}
bool comp(question a,question b)
{
if (a.l!=b.l) return (a.l<b.l);
else if (a.r!=b.r) return a.r<b.r;
else return a.id<b.id;
}
void change(int s)
{
int i,j,t,end;
t=a[s];
tmex[s]=0;
end=next[s];
if (end==0) end=n;
for (i=end;i>s;i--)
{
if (tmex[i]>t) tmex[i]=t;
else break;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
memset(b,false,sizeof(b));
for (i=1;i<=n;i++)
{
if (b[a[i]]) next[c[a[i]]]=i-1;
else next[c[a[i]]]=n;
c[a[i]]=i;
b[a[i]]=true;
}
t=0;
memset(b,false,sizeof(b));
for (i=1;i<=n;i++)
{
b[a[i]]=true;
while (a[i]==t || b[t]) t++;
tmex[i]=t;
}
build(1,1,n);
for (i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,comp);
last=1;
for (i=1;i<=m;i++)
{
if (q[i].l==last)
{
ans[q[i].id]=tmex[q[i].r];
}
else
{
for (j=last;j<q[i].l;j++) change(j);
ans[q[i].id]=tmex[q[i].r];
}
last=q[i].l;
}
for (i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}