Queue Aggregation
(datastructure/queueaggregation.hpp)

• View this file on GitHub
• Last update: 2020-08-29 20:31:38+09:00
• Include: #include "datastructure/queueaggregation.hpp"

概要

全体を二項演算$f$で畳み込んだものを$O(1)$で答えられるキュー.

渡す$f$は結合律を満たす必要がある.

• 結合律 : $f(f(x, y), z) = f(x, f(y, z))$

計算量

$O(1)$

使用例

• QueueAggregation<int> swag([](int a, int b){ return min(a, b); }) : 最小クエリを処理する SWAG.
• swag.emplace(x) : $x$を追加.
• swag.pop() : swagからpop.
• swag.query() : 全体を$f$で畳んだ結果.

Verified with

• test/yukicoder/1036.test.cpp

Code

/**
* @brief Queue Aggregation
* @docs docs/datastructure/queueaggregation.md
*/

template <typename T>
struct QueueAggregation {
    using F = function<T(T, T)>;
    stack<pair<T, T>> st_f, st_b;  // {val, sum}
    const F func;
    const T IDENT;
    QueueAggregation(const F f, const T IDENT)
        : func(f), IDENT(IDENT) {
        st_f.emplace(IDENT, IDENT);
        st_b.emplace(IDENT, IDENT);
    }
    // remove sentinel
    int size() const { return (int)st_f.size() + (int)st_b.size() - 2; }
    bool empty() const { return size() == 0; }
    T query() {
        return func(st_f.top().second, st_b.top().second);
    }
    void emplace(const T &x) {
        T merged = func(st_b.top().second, x);
        st_b.emplace(x, merged);
    }
    void pop() {
        assert(not empty());
        if (st_f.size() == 1) {  // <=> st_f.empty()
            st_f.emplace(st_b.top().first, st_b.top().first);
            st_b.pop();
            while (st_b.size() != 1) {
                T merged = func(st_b.top().first, st_f.top().second);
                st_f.emplace(st_b.top().first, merged);
                st_b.pop();
            }
        }
        st_f.pop();
    }
};

#line 1 "datastructure/queueaggregation.hpp"
/**
* @brief Queue Aggregation
* @docs docs/datastructure/queueaggregation.md
*/

template <typename T>
struct QueueAggregation {
    using F = function<T(T, T)>;
    stack<pair<T, T>> st_f, st_b;  // {val, sum}
    const F func;
    const T IDENT;
    QueueAggregation(const F f, const T IDENT)
        : func(f), IDENT(IDENT) {
        st_f.emplace(IDENT, IDENT);
        st_b.emplace(IDENT, IDENT);
    }
    // remove sentinel
    int size() const { return (int)st_f.size() + (int)st_b.size() - 2; }
    bool empty() const { return size() == 0; }
    T query() {
        return func(st_f.top().second, st_b.top().second);
    }
    void emplace(const T &x) {
        T merged = func(st_b.top().second, x);
        st_b.emplace(x, merged);
    }
    void pop() {
        assert(not empty());
        if (st_f.size() == 1) {  // <=> st_f.empty()
            st_f.emplace(st_b.top().first, st_b.top().first);
            st_b.pop();
            while (st_b.size() != 1) {
                T merged = func(st_b.top().first, st_f.top().second);
                st_f.emplace(st_b.top().first, merged);
                st_b.pop();
            }
        }
        st_f.pop();
    }
};

Back to top page