题目描述

有一个长度为$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

样例输出

1
2
3
0
3

数据范围

对于$30%$的数据:$1\leq n,m\leq1000$

对于$100%$的数据:$1\leq n,m\leq 200000,0\leq a_i\leq 10^9,1\leq l\leq r\leq n$

菜鸡的咆哮

考虑建立权值线段树,维护每一个权值在原数组中最后一次出现的下标。

对于查询$[l,r]$,取出$r$对应的主席树,寻找最后一次出现下标小于$l$的最小值。

$a_i$的上界是$10^9$,直接存肯定不行。

但我们可以发现每次询问的结果一定在$[1,n+1]$中。为什么?

如果询问的结果是$n+2$,那$n$个数一定对应$[1,n+1]$中所有的数。

$n+1>n$,显然不可能。

所以对于大于$n$的数,我们当作$n+1$处理即可。

代码

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m; 
int num[maxn],xx[maxn];
int tail;
int root[maxn];
int ls[30*maxn];
int rs[30*maxn];
int minn[30*maxn];
void push_up(int k){
    minn[k]=min(minn[ls[k]],minn[rs[k]]);
}
int clone(int k){
    tail++;
    ls[tail]=ls[k];
    rs[tail]=rs[k];
    minn[tail]=minn[k];
    return tail;
}
void build(int &k,int l,int r){
    k=++tail;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls[k],l,mid);
    build(rs[k],mid+1,r);
}
void insert(int &k,int l,int r,int x){
    k=clone(k);
    if(l==r){minn[k]=xx[l];return;}
    int mid=(l+r)>>1;
    if(x<=mid) insert(ls[k],l,mid,x);
    else insert(rs[k],mid+1,r,x);
    push_up(k);
}
int ask(int k,int l,int r,int x){
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(minn[ls[k]]<x) return ask(ls[k],l,mid,x);
    else return ask(rs[k],mid+1,r,x);
}
int main(){
    scanf("%d%d",&n,&m);
    build(root[0],1,n);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        num[i]++;
        if(num[i]>n) num[i]=n-1;
    }
    for(int i=1;i<=m;i++){
        xx[num[i]]=i;
        root[i]=root[i-1];
        insert(root[i],1,n,num[i]);    
    }
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        printf("%d\n",ask(root[b],1,n,a)-1);
    } 
    return 0;
}