Sliding Window Minimum
(library/datastructure/sliding_window_minimum.hpp)

• View this file on GitHub
• Last update: 2022-10-30 21:37:43+09:00
• Include: #include "library/datastructure/sliding_window_minimum.hpp"

Sliding Window Minimum

長さ $N$ の列 $A=(A_0,\ldots, A_{N-1})$ と $0$ で初期化された整数 $l,r$ に対して、次の操作を行う。

• $\mathrm{proc\_right}$ : $r\leftarrow r + 1$ とする。操作前の時点で $r=N$ の場合、この操作はできない。
• $\mathrm{proc\_left}$ : $l\leftarrow l + 1$ とする。操作前の時点で $l=r$ の場合、この操作はできない。
• $\mathrm{query}$ : $\displaystyle \min _ {l\leq i\lt r} A _ i$ を返す。
• $\mathrm{arg\_query}$ : $\displaystyle \mathop{\underset{l\leq i\lt r}{\mathrm{arg}\min}} A _ i$ を返す。

$\mathrm{proc\_right}$ は償却 $\Theta(1)$ 時間、その他は最悪 $\Theta(1)$ 時間である。

テンプレート引数の第二引数によって、$\min$ と $\max$ のどちらを計算するか、また $\mathrm{arg\_query}$ において等しい値が複数ある場合により小さい添字を優先するか、より大きい添字を優先するかの挙動を選択することが出来る。

suisen::prioritizing_mode 名前空間にテンプレート引数の第二引数に与えるための比較器の型エイリアスが定義されている。意味は次の通り。

• suisen::prioritizing_mode::left_most_min<T>
  • $\mathrm{query}$ : $\displaystyle \min _ {l\leq i\lt r} A _ i$ を返す。
  • $\mathrm{arg\_query}$ : $\displaystyle \mathop{\underset{l\leq i\lt r}{\mathrm{arg}\min}} A _ i$ を返す。最小値を達成する添字が複数ある場合は、添字が 最小 のものを返す。
• suisen::prioritizing_mode::right_most_min<T>
  • $\mathrm{query}$ : $\displaystyle \min _ {l\leq i\lt r} A _ i$ を返す。
  • $\mathrm{arg\_query}$ : $\displaystyle \mathop{\underset{l\leq i\lt r}{\mathrm{arg}\min}} A _ i$ を返す。最小値を達成する添字が複数ある場合は、添字が 最大 のものを返す。
• suisen::prioritizing_mode::left_most_max<T>
  • $\mathrm{query}$ : $\displaystyle \max _ {l\leq i\lt r} A _ i$ を返す。
  • $\mathrm{arg\_query}$ : $\displaystyle \mathop{\underset{l\leq i\lt r}{\mathrm{arg}\max}} A _ i$ を返す。最小値を達成する添字が複数ある場合は、添字が 最小 のものを返す。
• suisen::prioritizing_mode::left_most_min<T>
  • $\mathrm{query}$ : $\displaystyle \max _ {l\leq i\lt r} A _ i$ を返す。
  • $\mathrm{arg\_query}$ : $\displaystyle \mathop{\underset{l\leq i\lt r}{\mathrm{arg}\max}} A _ i$ を返す。最小値を達成する添字が複数ある場合は、添字が 最大 のものを返す。

Verified with

• test/src/datastructure/sliding_window_minimum/DSL_3_D.test.cpp

Code

#ifndef SUISEN_SLIDING_WINDOW_MINIMUM
#define SUISEN_SLIDING_WINDOW_MINIMUM

#include <cassert>
#include <vector>
#include <queue>
#include <type_traits>

namespace suisen {
namespace prioritizing_mode {
    template <typename T>
    using left_most_min  = std::greater<T>;
    template <typename T>
    using right_most_min = std::greater_equal<T>;
    template <typename T>
    using left_most_max  = std::less<T>;
    template <typename T>
    using right_most_max = std::less_equal<T>;
}

template <
    typename T, typename Comparator = prioritizing_mode::left_most_min<T>,
    std::enable_if_t<std::is_invocable_r_v<bool, Comparator, T, T>, std::nullptr_t> = nullptr
>
class sliding_window_minimum {
    public:
        template <typename Gen, std::enable_if_t<std::is_invocable_r_v<T, Gen, int>, std::nullptr_t> = nullptr>
        sliding_window_minimum(int n, Gen gen) : _n(n), _a(n) {
            for (int i = 0; i < _n; ++i) _a[i] = gen(i);
        }
        void proc_right() {
            assert(_r < _n);
            T v = _a[_r];
            while (not _dq.empty() and _cmp(_a[_dq.back()], v)) _dq.pop_back();
            _dq.push_back(_r++);
        }
        void proc_right(int to_index) {
            while (_r < to_index) proc_right();
        }
        void proc_left() {
            assert(_l < _r);
            if (_dq.front() == _l) _dq.pop_front();
            ++_l;
        }
        void proc_left(int to_index) {
            while (_l < to_index) proc_left();
        }
        void proc(int new_l, int new_r) {
            proc_right(new_r), proc_left(new_l);
        }
        int arg_query() const {
            assert(_l < _r);
            return _dq.front();
        }
        T query() const {
            return _a[arg_query()];
        }

        int get_left() const {
            return _l;
        }
        int get_right() const {
            return _r;
        }
        int get_window_size() const {
            return _r - _l;
        }
    private:
        const int _n;
        int _l = 0, _r = 0;
        std::vector<T> _a;
        std::deque<int> _dq;
        Comparator _cmp;
};
} // namespace suisen

#endif // SUISEN_SLIDING_WINDOW_MINIMUM

#line 1 "library/datastructure/sliding_window_minimum.hpp"



#include <cassert>
#include <vector>
#include <queue>
#include <type_traits>

namespace suisen {
namespace prioritizing_mode {
    template <typename T>
    using left_most_min  = std::greater<T>;
    template <typename T>
    using right_most_min = std::greater_equal<T>;
    template <typename T>
    using left_most_max  = std::less<T>;
    template <typename T>
    using right_most_max = std::less_equal<T>;
}

template <
    typename T, typename Comparator = prioritizing_mode::left_most_min<T>,
    std::enable_if_t<std::is_invocable_r_v<bool, Comparator, T, T>, std::nullptr_t> = nullptr
>
class sliding_window_minimum {
    public:
        template <typename Gen, std::enable_if_t<std::is_invocable_r_v<T, Gen, int>, std::nullptr_t> = nullptr>
        sliding_window_minimum(int n, Gen gen) : _n(n), _a(n) {
            for (int i = 0; i < _n; ++i) _a[i] = gen(i);
        }
        void proc_right() {
            assert(_r < _n);
            T v = _a[_r];
            while (not _dq.empty() and _cmp(_a[_dq.back()], v)) _dq.pop_back();
            _dq.push_back(_r++);
        }
        void proc_right(int to_index) {
            while (_r < to_index) proc_right();
        }
        void proc_left() {
            assert(_l < _r);
            if (_dq.front() == _l) _dq.pop_front();
            ++_l;
        }
        void proc_left(int to_index) {
            while (_l < to_index) proc_left();
        }
        void proc(int new_l, int new_r) {
            proc_right(new_r), proc_left(new_l);
        }
        int arg_query() const {
            assert(_l < _r);
            return _dq.front();
        }
        T query() const {
            return _a[arg_query()];
        }

        int get_left() const {
            return _l;
        }
        int get_right() const {
            return _r;
        }
        int get_window_size() const {
            return _r - _l;
        }
    private:
        const int _n;
        int _l = 0, _r = 0;
        std::vector<T> _a;
        std::deque<int> _dq;
        Comparator _cmp;
};
} // namespace suisen

Back to top page