Codeforce 1417 C. k-Amazing Numbers 解析(思維)

今天我們來看看CF1417C
題目連結

題目
略，請直接看原題。

前言

我實作好慢…

想法

只要注意到，真正重要的是對於某個數字，區間至少要多大才可以每個區間都包含到它。因此我們維護對於每種數字，其和下一個同種數字的最大距離，且還需要考慮元素到頭和到尾的距離。
如此一來就可以知道對於每種數字最短需要多大的區間。之後只要先$ans[dis[數字種類]]=min(ans[dis[數字種類]],數字種類)$，接著維護解答陣列的最小值前綴即可。

程式碼:

const int _n=3e5+10,MAXB=20;  
int t,n,a[_n],prev[_n],dis[_n],ans[_n],last[_n];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    cin>>n;rep(i,1,n+1)cin>>a[i];  
    rep(i,0,n+1)ans[i]=dis[i]=prev[i]=last[i]=0;  
    rep(i,1,n+1)ans[i]=1e9;  
    rep(i,1,n+1){  
      dis[a[i]]=max(dis[a[i]],i-prev[a[i]]);  
      last[a[i]]=i;  
      prev[a[i]]=i;  
    }rep(i,1,n+1)if(last[i])dis[i]=max(dis[i],n+1-last[i]);  
    rep(i,1,n+1)ans[dis[i]]=min(ans[dis[i]],i);  
    rep(i,2,n+1)ans[i]=min(ans[i],ans[i-1]);  
    rep(i,1,n+1)cout<<(ans[i]==1e9?-1:ans[i])<<' '; cout<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission