求问玄学问题,玄关
查看原帖
求问玄学问题,玄关
1070754
lijunxi20231818楼主2025/2/7 16:20

这是我的 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;
}
2025/2/7 16:20
加载中...