第 `i` 个数所属的块是 `(i-1)/len+1`
#### AC code：
```
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200001
int n, m, res, lasb(-1), l(1), r, minn;
int L[MAXN];
int a[MAXN], bu[MAXN], ans[MAXN], bu2[MAXN];
struct Que{int l, r, id;}que[MAXN];
void del(int x, int &res){
if (!(--bu[x])) res = min(res, x);
}
void rem(int x){++bu[x];}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i(1); i<=n; ++i){
cin >> a[i];
if (a[i] <= n+1) ++bu[a[i]];
}
while (bu[res]) ++res;
for (int i(1); i<=m; ++i){
cin >> que[i].l >> que[i].r;
que[i].id = i;
}
int len(sqrt(n)), tot((n-1)/len+1);
for (int i(1); i<=tot; ++i) L[i] = (i-1)*len+1; // 1
sort(que+1, que+m+1, [len](Que a, Que b){
if ((a.l-1)/len == (b.l-1)/len/*第一处修改*/) return a.r > b.r;
return (a.l-1)/len < (b.l-1)/len;/*第二处修改*/
});
r = n;
for (int i(1); i<=m; ++i){
if ((que[i].l-1)/len == (que[i].r-1)/len/*第三处修改*/){
for (int j(que[i].l); j<=que[i].r; ++j) ++bu2[a[j]];
int tmp(0);
while (bu2[tmp]) ++tmp;
for (int j(que[i].l); j<=que[i].r; ++j) --bu2[a[j]];
ans[que[i].id] = tmp;
continue;
}
if (lasb ^ ((que[i].l-1)/len+1)/*第五处修改*/){
while (r < n) rem(a[++r]);
while (l < L[(que[i].l-1)/len+1]/*第六处修改*/) del(a[l++], res); // 2
lasb = (que[i].l-1)/len+1;/*第七处修改*/
minn = res;
}
while (r > que[i].r) del(a[r--], minn);
int tmp(minn), lp(l);
while (lp < que[i].l) del(a[lp++], tmp);
while (lp > l) rem(a[--lp]);
ans[que[i].id] = tmp;
}
for (int i(1); i<=m; ++i) cout << ans[i] << '\n';
return 0;
}
by pig1121 @ 2024-02-09 13:34:53
@[rainygame](/user/804607)
by pig1121 @ 2024-02-09 13:35:48