普通莫队的复杂度应该为 $O(1)$ 删除、$O(n)$ 添加，事实证明正常写也只能拿到 88pts。但是我尝试着在对询问排序时乱搞了一下，成功地通过了本题。

#include <bits/stdc++.h>
namespace xuan_never {
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;
#define fi first
#define se second
const int maxn = 2e5 + 50, maxs = 500;
int n, m, T, a[maxn], ans[maxn];
ppi Q[maxn];
int cnt[maxn], mex;
void upd(int x, int v) {
	cnt[a[x]] += v;
	if (cnt[a[x]] == 0 && a[x] < mex) mex = a[x];
	else if (a[x] == mex) {
		while (cnt[mex]) ++mex;
	}
}
void init() {}
void mian() {
	init();
	cin >> n >> m;
	T = max(sqrt((double)n * n / m), 1.0);
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	for (int i = 1; i <= m; ++i)
		cin >> Q[i].fi.fi >> Q[i].fi.se, Q[i].se = i;
	sort(Q + 1, Q + 1 + m, [](ppi x, ppi y) {
		if ((x.fi.fi - 1) / T == (y.fi.fi - 1) / T) {
			if ((x.fi.se - 1) / T == (y.fi.se - 1) / T) // 乱搞
				return x.fi.fi < y.fi.fi;
			return x.fi.se > y.fi.se;
		}
		return x.fi.fi < y.fi.fi;
	});
	for (int i = 0, j = 1, l = 1, r = 0, ql, qr; i * T + 1 <= n && j <= m; ++i) {
		if ((Q[j].fi.fi - 1) / T != i) continue;
		ql = i * T + 1, qr = Q[j].fi.se;
		while (r < qr) upd(++r, 1);
		while (l > ql) upd(--l, 1);
		while (r > qr) upd(r--, -1);
		while (l < ql) upd(l++, -1);
		// cerr << ql << ' ' << qr << "  " << mex << '\n';
		while (j <= m && (Q[j].fi.fi - 1) / T == i) {
			ql = Q[j].fi.fi, qr = Q[j].fi.se;
			while (r < qr) upd(++r, 1);
			while (l > ql) upd(--l, 1);
			while (r > qr) upd(r--, -1);
			while (l < ql) upd(l++, -1);
			ans[Q[j].se] = mex;
			++j;
		}
	}
	for (int i = 1; i <= m; ++i)
		 cout << ans[i] << '\n';
}
} using namespace xuan_never;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
//	init();
	int T = 1;
//	cin >> T;
	while (T--) mian();
	return 0;
}

个人感觉这个代码时间复杂度是不正确的，故发此帖求证/求hack。