src/old/SlideMin.hpp

• View this file on GitHub
• Last update: 2020-04-25 17:31:02+09:00
• Include: #include "src/old/SlideMin.hpp"

Code

// 自分を含んだK個前までの中での最小値のindexの配列を返す
// 最小(最大)値のindexを返すことに注意!
template <class T = int> vector<int> slide_min(const vector<T>& a, int w, function<bool(T, T)> cmp = less<T>()) {
    int n = a.size();
    vector<int> ret(n);
    deque<int> dq;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && !cmp(a[dq.back()], a[i])) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (dq.front() <= i - w) {
            dq.pop_front();
        }
        ret[i] = dq.front();
    }
    return ret;
}

#line 1 "src/old/SlideMin.hpp"
// 自分を含んだK個前までの中での最小値のindexの配列を返す
// 最小(最大)値のindexを返すことに注意!
template <class T = int> vector<int> slide_min(const vector<T>& a, int w, function<bool(T, T)> cmp = less<T>()) {
    int n = a.size();
    vector<int> ret(n);
    deque<int> dq;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && !cmp(a[dq.back()], a[i])) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (dq.front() <= i - w) {
            dq.pop_front();
        }
        ret[i] = dq.front();
    }
    return ret;
}

Back to top page