data-structure/sliding-window-minimum.hpp

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "data-structure/sliding-window-minimum.hpp"

Verified with

• verify/verify-aoj-dsl/aoj-dsl-3-d.test.cpp

Code

#pragma once

// return dat | dat[i] := ( answer of range [i - K, i) )
// T : data type
// f : compare function
// K : width of window
template <typename T, typename F>
vector<T> SlideWindowMinimum(vector<T> &v, F f, int K) {
  vector<T> dat;
  int N = v.size();
  dat.resize(N + 1);
  dat[0] = 0;
  deque<int> q;
  for (int i = 0; i < K - 1; i++) {
    while (!q.empty() && (f(v[i], v[q.back()]) == v[i])) q.pop_back();
    q.push_back(i);
    dat[i + 1] = v[q.front()];
  }
  for (int i = K; i < N + 1; i++) {
    T cur = v[i - 1];
    while (!q.empty() && (f(cur, v[q.back()]) == cur)) q.pop_back();
    q.push_back(i - 1);
    dat[i] = v[q.front()];
    if (q.front() == i - K) q.pop_front();
  }
  return dat;
}

#line 2 "data-structure/sliding-window-minimum.hpp"

// return dat | dat[i] := ( answer of range [i - K, i) )
// T : data type
// f : compare function
// K : width of window
template <typename T, typename F>
vector<T> SlideWindowMinimum(vector<T> &v, F f, int K) {
  vector<T> dat;
  int N = v.size();
  dat.resize(N + 1);
  dat[0] = 0;
  deque<int> q;
  for (int i = 0; i < K - 1; i++) {
    while (!q.empty() && (f(v[i], v[q.back()]) == v[i])) q.pop_back();
    q.push_back(i);
    dat[i + 1] = v[q.front()];
  }
  for (int i = K; i < N + 1; i++) {
    T cur = v[i - 1];
    while (!q.empty() && (f(cur, v[q.back()]) == cur)) q.pop_back();
    q.push_back(i - 1);
    dat[i] = v[q.front()];
    if (q.front() == i - K) q.pop_front();
  }
  return dat;
}

Back to top page