文件详细信息

下载本文件

本文件的大小为 1997 字节。

/*
## 题目大意

有一个长度为 $n$ 的数组 $a_1,a_2,\cdots,a_n$。$m$ 次询问，每次询问一个区间内最小没有出现过的自然数。

保证 $1 \le n,m \le 2 \times 10^5$，$0 \le a_i \le 10^9$。
*/
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
void chkmin(T&a,const T b){
	if(a>b)a=b;
}
const int maxn=200000,maxm=200000,maxtot=448;
int n,m,B,tot,a[maxn+1],b[maxn+1],mex,cur,tmp,belong[maxn+1],l[maxtot+1],r[maxtot+1],cnt[maxn+1];
struct OP{
	int l,r,id;
}q[maxm+1];
bool operator<(const OP a,const OP b){
	return belong[a.l]!=belong[b.l]?a.l<b.l:a.r>b.r;
}
int ans[maxm+1];
void del(const int x){
	if(a[x]<mex&&--cnt[a[x]]==0)chkmin(cur,a[x]);
}
void add(const int x){
	if(a[x]<mex)cnt[a[x]]++;
}
int main(){
	read(n),read(m);
	B=sqrt(n),tot=(n+B-1)/B;
	for(int i=1;i<=n;i++)read(a[i]);
	memcpy(b+1,a+1,sizeof(int)*n);
	std::sort(b+1,b+n+1);
	b[0]=-1;
	for(int i=1;i<=n;i++)
		if(b[i]>=b[i-1]+2){
			mex=b[i-1]+1;
			break;
		}
	if(!mex)mex=b[n]+1;
	for(int i=1;i<=n;i++)
		if(a[i]<mex)
			cnt[a[i]]++;
	for(int i=1;i<=tot;i++){
		l[i]=r[i-1]+1,r[i]=std::min(r[i-1]+B,n);
		for(int j=l[i];j<=r[i];j++)belong[j]=i;
	}
	for(int i=1;i<=m;i++){
		read(q[i].l),read(q[i].r);
		q[i].id=i;
	}
	std::sort(q+1,q+m+1);
	int nl=1,nr=n;
	for(int i=1;i<=m;i++){
		int x=l[belong[q[i].l]];
		if(i==1||belong[q[i].l]!=belong[q[i-1].l]){
			while(nl>1)add(--nl);
			while(nr<n)add(++nr);
			cur=mex;
			while(nl<x)del(nl++);
		}
		while(nr>q[i].r)del(nr--);
		tmp=cur;
		while(nl<q[i].l)del(nl++);
		ans[q[i].id]=cur;
		while(nl>x)add(--nl);
		cur=tmp;
	}
	for(int i=1;i<=m;i++)write(ans[i]),putchar('\n');
	return 0;
}