slide_max.hpp

• View this file on GitHub
• Last update: 2024-09-23 18:33:28+09:00
• Include: #include "slide_max.hpp"

Code

// res[i] = op (i-k, i]
template <class S, auto op>
vector<S> slide_max(vector<S> a, int k) {
    static_assert(is_convertible_v<decltype(op), function<S(S, S)>>, "op must work as S(S, S)");
    int n = a.size();
    deque<pair<int, S>> deq;
    vector<S> res(n);
    for (int i = 0; i < n; ++i) {
        while (!deq.empty() && deq.front().first <= i - k) deq.pop_front();
        while (!deq.empty() && op(deq.back().second, a[i]) == a[i]) deq.pop_back();
        deq.emplace_back(i, a[i]);
        res[i] = deq.front().second;
    }
    return res;
}

#line 1 "slide_max.hpp"
// res[i] = op (i-k, i]
template <class S, auto op>
vector<S> slide_max(vector<S> a, int k) {
    static_assert(is_convertible_v<decltype(op), function<S(S, S)>>, "op must work as S(S, S)");
    int n = a.size();
    deque<pair<int, S>> deq;
    vector<S> res(n);
    for (int i = 0; i < n; ++i) {
        while (!deq.empty() && deq.front().first <= i - k) deq.pop_front();
        while (!deq.empty() && op(deq.back().second, a[i]) == a[i]) deq.pop_back();
        deq.emplace_back(i, a[i]);
        res[i] = deq.front().second;
    }
    return res;
}

Back to top page