题解：P13339 [EGOI 2025] Gift Boxes / 礼品盒

· · 题解

显然是可以双指针的。

考虑左侧取得一个极长的串满足 [0,l] 中没有重复的数，在该情况下从右侧取得一个与 [0,l] 中没有重复的数且 [r,n-1] 中也没有重复的数。

令 l 逐渐减小，并逐渐更新 r，记录下当前情况下的最优 [l,r] 即可，时间复杂度线性。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int 
using namespace std;
const ll N=5e5+10;
ll T,n,a[N],tong[N],cnt;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    ll l=0,r=n+1;
    while(tong[a[r-1]]==0){
        r--;cnt++;tong[a[r]]++; 
    }
    while(tong[a[l+1]]==0){
        l++;cnt++;tong[a[l]]++; 
    }
    ll ansL=0,ansR=n+1,anscnt=0;
    for(;r<=n+1;r++){
        while(tong[a[l+1]]==0){
            l++;cnt++;tong[a[l]]++; 
        }
        if(cnt>=anscnt){
            if(cnt==anscnt){
                if(r-l<ansR-ansL) ansR=r,ansL=l;
            }
            else{
                anscnt=cnt;
                ansR=r,ansL=l;
            }
        }
        tong[a[r]]--;
        cnt--;
    }
    cout<<ansL<<' '<<ansR-2;
    return 0;
}