スライド最小値 Sliding Window Minimum Algorithm

  • Quiz
  • AC
  • 解説
    • 蟻本p301にある
    • 最初はmultisetを使ってO(NlogN)で解いたが、スライド最小値を使うとO(N)となる
      • (N=1000000なのでNlogNだと2x107となり各テストケース0.2秒かかりうるので遅さを感じた)
    • dequeを使い、範囲Lの中で最小のインデックスがdequeの左端にあることを維持すればよい
    • 範囲内のインデックスであっても使わないことが確定しているものは早期に捨てる（while内でpop_backしている箇所）
int main(){
    // input
    ll N,L;
    cin>>N>>L;

    VI A(N);
    rep(i, N) cin >> A[i];

    deque<ll> que;
    que.push_back(0);
    FOR(i,1,L){
      while(que.size()>0 && A[que.back()]>=A[i]){
        que.pop_back();
      }
      que.push_back(i);
    }
    VI Ans;
    Ans.push_back(A[que.front()]);
    
    FOR(i,L,N){
      // 新しく足すのがA[i]

      if(que.front()==i-L) que.pop_front(); // 範囲外なので除去

      // A[i]を足す
      while(que.size()>0 && A[que.back()]>=A[i]){
        que.pop_back();
      }
      que.push_back(i);    
      Ans.push_back(A[que.front()]);
    }
    print_vector(Ans);

    return 0;
}

英名