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

· · 题解

题意可以理解为：我们选出一个区间 [l,r]，使得我们没有选到的数中没有重复的数字。

考虑维护两个没有被选择的段，下文设其为 [1,L] 和 [R,n]。

首先我们枚举每一个 L，然后我们发现左边区间的每一个数都不能在右边出现过，所以我们可以预处理出来左边每一个数其在右边第一次出现的位置，设这个位置为 x，那么则有 R > \max x，所以我们想求这个最小的选择的区间长度就是区间 [L+1,R-1] 了。

上面的 \max x 可以在枚举 L 的时候直接求一个前缀最大值。

然而这并没有结束，可能右边自己出现了两个相同的，或者左边自己出现了两个相同的，判断一下即可。

注意左边一点也不选的情况，时间复杂度 O(n)。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
constexpr int N=5*1e5+10;
int _=1,T,n,R=0,ansL,ansR,ans=2e9,ok=0,a[N],maxn[N],ton[N];
bool flg=0;
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}inline void files(){
    freopen("gift.in","r",stdin);
    freopen("gift.out","w",stdout);
}inline void clr(){
//  Don't forget!

}bool Test_MLE_end;
signed main(){
//  printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
    files(); 
//  _=reads();
    while(_--){
        clr();T=reads(),n=reads();
        for(int i=1;i<=n;i++) a[i]=reads();
        for(int i=n;i>=1;i--){
            if(!maxn[a[i]]) maxn[a[i]]=i+1;
            if(!ton[a[i]]) ton[a[i]]=1;
            else if(!flg&&ton[a[i]]) ok=i+1,flg=1;
        }memset(ton,0,sizeof(ton));
        if(ok<ans) ans=ok,ansL=1,ansR=ok-1;
        for(int i=0;i<T;i++) maxn[i]=max(maxn[i],ok);
        for(int i=1;i<=n;i++){
            if(!ton[a[i]]) ton[a[i]]=1;
            else{ok=i-1;break;}
        }
        for(int L=1;L<=ok;L++){
            R=max(R,maxn[a[L]]);
            int pl=L+1,pr=R-1;
            if(pl>pr) continue;
            if(pr-pl+1<ans){
                ans=pr-pl+1;
                ansR=pr,ansL=pl;
            }
        }printf("%d %d\n",ansL-1,ansR-1);
    }return 0;
}
/*
2 3
0 1 0
*/