怎么感觉所有人都写了离线，还写的很复杂（
这个题完全是可以在线的，而且非常好写。复杂度 $O(n\sqrt{n}+q\sqrt{n})$。$n$ 是序列长度，$q$ 是询问数。
如果 $l$ 固定的话显然是好做的。直接向右推 $r$ 即可。$r$ 固定同理。
那这个题 $l$ 不固定怎么办，考虑选取 $\sqrt{n}$ 个点，向左向右推，求出这些区间的答案。显然时空复杂度均为 $O(n\sqrt{n})$。
然后我们考虑查询。对于一个区间 $l,r$，设 $l'$ 为 $l$ 右边第一个被选取的点，$r'$ 为 $r$ 左边第一个被选取的点，$[l,r']$ 和 $[l',r]$ 的答案可以 $O(1)$ 求出，剩下的就是 $[l,l')$ 和 $(r',r]$ 两端区间之间的贡献，把 $[l,l')$ 的所有数丢桶里，扫 $(r',r]$ 查即可。因为这两段区间长度都是 $O(\sqrt{n})$，所以单次查询复杂度为 $O(\sqrt{n})$。
代码出奇地好写。
#include<bits/stdc++.h>
#define F(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
int n, m, q, a[100005], f[320][100005], b[100005];
int kc, ks, L[505], R[505], B[100005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
F(i, 1, n) cin >> a[i];
kc = sqrt(n), ks = (n + kc - 1) / kc;
F(i, 1, ks){
L[i] = R[i - 1] + 1, R[i] = i == ks ? n : L[i] + kc - 1;
F(j, L[i], R[i]) B[j] = i;
F(j, L[i], n){
if (!b[a[j]]) b[a[j]] = j;
f[i][j] = max(f[i][j - 1], j - b[a[j]]);
}
F(j, 1, m) b[j] = 0;
b[a[L[i]]]++;
for (int j = L[i] - 1; j; j--){
if (!b[a[j]]) b[a[j]] = j;
f[i][j] = max(f[i][j + 1], b[a[j]] - j);
}
F(j, 1, m) b[j] = 0;
}
cin >> q;
while (q--){
int l, r, ans = 0;
cin >> l >> r;
if (B[l] == B[r]){
F(i, l, r){
if (!b[a[i]]) b[a[i]] = i;
ans = max(ans, i - b[a[i]]);
}
F(i, l, r) b[a[i]] = 0;
}else{
ans = max(f[B[l] + 1][r], f[B[r]][l]);
F(i, l, R[B[l]]) if (!b[a[i]]) b[a[i]] = i;
F(i, L[B[r]], r) if (b[a[i]]) ans = max(ans, i - b[a[i]]);
F(i, l, R[B[l]]) b[a[i]] = 0;
}
cout << ans << "\n";
}
return 0;
}