题解：先莫队排序一波，然后对权值进行分块，找出第一个没有填满的块，直接for一遍找答案。
除了bzoj3339以外，另外两道题Ai范围都是1e9。显然最劣情况下答案是N，所以大于N的Ai都直接无视就可以。
由于求的是最小的自然数，自然数包括0，所以要额外处理一下含有0的块。我这里是直接把0拖出来放在第0块了。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
inline int rd(){
int f=,x=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=,maxm=,max_block=;
int N,M,A[maxn],l,r,block,Ans[maxm],vis[maxn],cnt[max_block],num,belong[maxn];
struct Q{
int id,l,r;
}q[maxm];
inline bool cmp(const Q&a,const Q&b){
if(belong[a.l]==belong[b.l])return a.r<b.r;
return a.l<b.l;
}
inline void Add(int x){
if(x<=N){
if(vis[x]==)cnt[belong[x]]++;
vis[x]++;
}
return;
}
inline void Del(int x){
if(x<=N){
vis[x]--;
if(vis[x]==)cnt[belong[x]]--;
}
return;
}
int main(){
N=rd();M=rd();
block=sqrt(N);
num=N/block;
if(N%block)num++;
for(int i=;i<=N;i++){
A[i]=rd();
belong[i]=(i-)/block+;
}
belong[]=;
for(int i=;i<=M;i++){
q[i].id=i;
q[i].l=rd();
q[i].r=rd();
}
sort(q+,q+M+,cmp);
l=;r=;
for(int i=;i<=M;i++){
int ql=q[i].l,qr=q[i].r,id=q[i].id;
while(l<ql)Del(A[l++]);
while(l>ql)Add(A[--l]);
while(r<qr)Add(A[++r]);
while(r>qr)Del(A[r--]);
if(cnt[]==){
Ans[id]=;
continue;
}
int t=-;
for(int j=;j<=num;j++){
if(j!=num&&cnt[j]!=block){
t=j;
break;
}
else if(cnt[j]!=N-(num-)*block) t=j;
}
if(t==-){
Ans[id]=N;
continue;
}
int f=(t-)*block+,toj=t*block;
for(int j=f;j<=toj;j++)
if(vis[j]==){
Ans[id]=j;
break;
}
}
for(int i=;i<=M;i++)printf("%d\n",Ans[i]);
return ;
}
By：AlenaNuna