题目描述
有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
输入
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
输出
一行一个数，表示每个询问的答案。
样例输入
5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
样例输出
1
2
3
0
3
2
3
0
3
提示
数据规模和约定
对于100%的数据：
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据：
1<=n,m<=1000
刚看到题可能有人会想建权值线段树然后维护区间出现数字次数，但有可能区间内出现的都是同一个数，无法判断。因为询问在l~r内最小没有出现过的数，所以可以建权值线段树，每个叶子节点记录这个权值最晚出现的时间，维护区间出现时间的最小值。对于询问l~r只需要在r时刻线段树中查询区间出现时间最小值小于l的就行了。
最后附上代码。
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mid (L+R)/2
using namespace std;
int n,m;
int x,y;
int cnt;
int a[200010];
int l[6000010];
int r[6000010];
int mx[6000010];
int root[200010];
int updata(int pre,int L,int R,int v,int c)
{
int rt=++cnt;
l[rt]=l[pre];
r[rt]=r[pre];
if(L==R)
{
mx[rt]=c;
}
else
{
if(v<=mid)
{
l[rt]=updata(l[pre],L,mid,v,c);
}
else
{
r[rt]=updata(r[pre],mid+1,R,v,c);
}
mx[rt]=min(mx[l[rt]],mx[r[rt]]);
}
return rt;
}
int query(int x,int L,int R,int v)
{
if(L>=R)
{
return L;
}
if(v>mx[l[x]])
{
return query(l[x],L,mid,v);
}
else
{
return query(r[x],mid+1,R,v);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
root[i]=updata(root[i-1],0,1e8,a[i],i);
}
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(root[y],0,1e8,x));
}
}