Codeforcdes 63 E. Subsegments

問題

項数nの数列a[i]および整数kが与えられる。
a[i]からa[i+k-1]のうち「2個以上現れない整数で最大のもの」を、
それぞれのi（0≦i≦n-k）に対して求めよ。
存在しない場合はNothingを出力せよ。

n≦10^5を満たす。

解法

スライド最小値っぽい問題……がn*log(k)のオーダーの解法でよい。
map c[v]:=見ている範囲における値vの出現回数
set s:=見ている範囲で、「1個だけ現れている整数」の集合

とすれば、見る範囲を1ずらした時、c[a[i]]++, c[a[i-k]]--として、
c[a[i]], c[a[i-k]]の値に併せてsを更新することがlog(k)でできる。
sの最大値もlog(k)で見ることができるので、全体でnlog(k)で計算できる。

ソースコード

int a[100000];
void ck(set<int> &s,map<int,int> &c,int v){
  if(c[v]==1)s.insert(v);
  else s.erase(v);
}
void out(set<int> &s){
  if(s.empty()){
    cout<<"Nothing"<<endl;
    return;
  }
  set<int>::iterator last=s.end(); last--;
  cout<<*last<<endl;
}

void run(){
  int n,k; cin>>n>>k;
  rep(i,n)cin>>a[i];
  
  set<int> s;
  map<int,int> c;
  
  rep(i,k){
    c[a[i]]++;
    ck(s,c,a[i]);
  }
  out(s);

  for(int i=k;i<n;i++){
    c[a[i-k]]--;
    ck(s,c,a[i-k]);
    
    c[a[i]]++;
    ck(s,c,a[i]);
    out(s);
  }
}