显然可以离线主席树，这里用莫队+分块做。分块的一个重要思想是实现修改与查询时间复杂度的均衡，这里莫队和分块互相弥补。
考虑暴力的分块做法，首先显然大于n的数直接忽略，于是将值域分成sqrt(n)份，每块记录块内的所有值是否在此当前区间内都已存在。
这样每次暴力从L到R分别放入这个表，最后从小到大询问每个块是否已满，若没有则在块内枚举第一个不存在的数。
注意到这样的总修改复杂度O(nq)，查询复杂度O(qsqrt(n))。
考虑莫队，将序列分成sqrt(n)份，使总修改复杂度变为O(nsqrt(n))。查询复杂度不变O(qsqrt(n))。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=200010,K=810; 7 int n,m,B,a[N],b[N],ans[N],cnt[K],s[K][K]; 8 struct P{ int l,r,id; }q[N]; 9 10 bool cmp(const P &x,const P &y){ return b[x.l]!=b[y.l] ? b[x.l]<b[y.l] : x.r<y.r; } 11 12 void add(int x){ 13 if (x>n) return; 14 int t=x%B; s[b[x]][t]++; if (s[b[x]][t]==1) cnt[b[x]]++; 15 } 16 17 void del(int x){ 18 if (x>n) return; 19 int t=x%B; s[b[x]][t]--; if (s[b[x]][t]==0) cnt[b[x]]--; 20 } 21 22 int Que(){ 23 rep(i,1,n/B+1){ 24 int t=min(n,i*B-1)-(i-1)*B+1; 25 if (cnt[i]==t) continue; 26 rep(j,(i-1)*B,min(n,i*B-1)) if (!s[i][j%B]) return j; 27 } 28 return n+1; 29 } 30 31 int main(){ 32 freopen("bzoj3585.in","r",stdin); 33 freopen("bzoj3585.out","w",stdout); 34 scanf("%d%d",&n,&m); B=800; b[0]=1; 35 rep(i,1,n) scanf("%d",&a[i]),b[i]=i/B+1; 36 rep(i,1,m) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; 37 sort(q+1,q+m+1,cmp); int L=1,R=0; 38 rep(i,1,m){ 39 while (R<q[i].r) R++,add(a[R]); 40 while (L>q[i].l) L--,add(a[L]); 41 while (R>q[i].r) del(a[R]),R--; 42 while (L<q[i].l) del(a[L]),L++; 43 ans[q[i].id]=Que(); 44 } 45 rep(i,1,m) printf("%d ",ans[i]); 46 return 0; 47 }