data-structure/slide-min.hpp

View this file on GitHub
Last update: 2023-03-13 02:01:43+09:00
Include: #include "data-structure/slide-min.hpp"

Verified with

test/aoj/DSL/DSL_3_D.test.cpp

Code

template <class T>
vector<T> slide_min(const vector<T> &a, int k){
  int n = (int)a.size();
  deque<T> que;
  vector<T> res(n);
  for(int i = 0; i < n + k - 1; i++){
    while(!que.empty() && i < n && a[que.back()] >= a[i]){
      que.pop_back();
    }
    que.push_back(i);
    if(i - k + 1 >= 0){
      res[i - k + 1] = a[que.front()];
      if(que.front() == i - k + 1) que.pop_front();
    }
  }
  return res;
}

#line 1 "data-structure/slide-min.hpp"
template <class T>
vector<T> slide_min(const vector<T> &a, int k){
  int n = (int)a.size();
  deque<T> que;
  vector<T> res(n);
  for(int i = 0; i < n + k - 1; i++){
    while(!que.empty() && i < n && a[que.back()] >= a[i]){
      que.pop_back();
    }
    que.push_back(i);
    if(i - k + 1 >= 0){
      res[i - k + 1] = a[que.front()];
      if(que.front() == i - k + 1) que.pop_front();
    }
  }
  return res;
}