3585: mex
Time Limit: 20 Sec Memory Limit: 128 MB
Description
有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
Input
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
Output
一行一个数，表示每个询问的答案。
Sample Input
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
Sample Output
1
2
3
0
3
2
3
0
3
HINT
数据规模和约定
对于100%的数据：
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据：
1<=n,m<=1000
Source
我们考虑建权值线段树，每个数字 x 保存它最后出现的位置
这样查询[l,r]，就是找第r棵主席树中第一个值< l 的
主席树上每个区间维护当前数中，权值从 l 到 r 中最后一次出现最靠左的位置
就是相当于维护区间最小值即可
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define M 6000100
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int rt[N],ls[M],rs[M],mn[M],cnt;
void add(int &p,int f,int l,int r,int x,int v)
{
p=++cnt;
if(l==r){mn[p]=v;return;}
ls[p]=ls[f];rs[p]=rs[f];
int mid=(l+r)>>;
if(x>mid) add(rs[p],rs[f],mid+,r,x,v);
else add(ls[p],ls[f],l,mid,x,v);
mn[p]=min(mn[ls[p]],mn[rs[p]]);
}
int query(int p,int l,int r,int v)
{
if(l==r) return l;
int mid=(l+r)>>;
if(mn[ls[p]]<v) return query(ls[p],l,mid,v);
else return query(rs[p],mid+,r,v);
}
int n,m,x,mx=1e8+;
int main()
{
n=read();m=read();
for(int i=;i<=n;i++){x=read();add(rt[i],rt[i-],,mx,x,i);}
int l,r;
for(int i=;i<=m;i++)
{
l=read();r=read();
printf("%d\n",query(rt[r],,mx,l));
}
return ;
}