这是我的 AC 代码,但是我如果改成注释里的 while 和 cur++ 就会 TLE 4pts,求问原因,玄关。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res = 0, flg = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') flg = -flg;
c = getchar();
}
while(c >= '0' && c <= '9'){
res = res * 10 + c - '0';
c = getchar();
}
return res * flg;
}
inline void write(int x){
if(x > 9) write(x / 10);
putchar('0' + x % 10);
}
const int maxn = 2e5 + 5;
int n, m, block, a[maxn], ans[maxn], lst[maxn], id[maxn], num[maxn], fst[maxn], clear[maxn], clearcnt;
struct Query{
int l, r, id;
} q[maxn];
int max(int x, int y){
return x < y ? y : x;
}
int baoli(int l, int r){
int first[maxn], res = 0;
for(int i = l; i <= r; i++) first[a[i]] = 0;
for(int i = l; i <= r; i++){
if(!first[a[i]]){
first[a[i]] = i;
}else{
res = max(res, i - first[a[i]]);
}
}
return res;
}
signed main(){
n = read();
block = sqrt(n);
for(int i = 1; i <= n; i++){
a[i] = read(); num[i] = a[i];
id[i] = (i - 1) / block + 1;
}
sort(num + 1, num + n + 1);
int numcnt = unique(num + 1, num + n + 1) - num - 1;
for(int i = 1; i <= n; i++){
a[i] = lower_bound(num + 1, num + numcnt + 1, a[i]) - num;
}
m = read();
for(int i = 1; i <= m; i++){
q[i].l = read(), q[i].r = read();
q[i].id = i;
}
sort(q + 1, q + m + 1, [](Query x, Query y){
if(id[x.l] != id[y.l]){
return id[x.l] < id[y.l];
}
return x.r < y.r;
});
int cur = 1;
for(int i = 1; i <= id[n]; i++){
int blockr = min(n, i * block);
int l = blockr + 1, r = blockr, res = 0;
clearcnt = 0;
// while(id[q[cur].l] == i){
for(; id[q[cur].l] == i; cur++){
int ql = q[cur].l, qr = q[cur].r;
if(id[qr] == i){
ans[q[cur].id] = baoli(ql, qr);
continue;
}
while(r < qr){
r++;
lst[a[r]] = r;
if(!fst[a[r]]){
fst[a[r]] = r;
clear[++clearcnt] = a[r];
}
res = max(res, r - fst[a[r]]);
}
int tmp = res;
while(l > ql){
l--;
if(lst[a[l]]){
res = max(res, lst[a[l]] - l);
}else{
lst[a[l]] = l;
}
}
ans[q[cur].id] = res;
while(l <= blockr){
if(lst[a[l]] == l){
lst[a[l]] = 0;
}
l++;
}
res = tmp;
// cur++;
}
for(int i = 1; i <= clearcnt; i++){
lst[clear[i]] = fst[clear[i]] = 0;
}
}
for(int i = 1; i <= m; i++){
write(ans[i]); putchar('\n');
}
return 0;
}