src/DataStructure/SlidingWindowAggregation.hpp

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

概要

モノイド列について、以下のクエリを全て償却O(1)で行える。

• push
• pop
• fold_all: 現在queueに入っている要素全ての合成

実際は半群に対して適用可能だが、実装の都合上モノイドにしている(半群には単位元を形式的に追加して使用できる)。

使用例

auto swag = make_swag<Int>([](Int x, Int y) { return std::gcd(x, y); }, 0);

メモ

stackを2つ用いてqueueを作る非常にシンプルなアルゴリズム。 償却計算量の凄さに感動した。
参考: https://snuke.hatenablog.com/entry/2018/09/18/135640

Verified with

• test/yukicoder/1036.test.cpp

Code

/// @docs src/DataStructure/SlidingWindowAggregation.md
template <class T, class F> struct SlidingWindowAggregation {
    const F op;
    const T e;
    std::stack<std::pair<T, T>> st1, st2;  // それぞれ、{val, acc}を要素に持つような前方向と後ろ方向のstack
    SlidingWindowAggregation(F op_, T e_) : op(op_), e(e_) { st1.emplace(e, e), st2.emplace(e, e); }
    int size() { return st1.size() + st2.size() - 2; }
    void push(T x) {
        T acc = op(st2.top().second, x);
        st2.emplace(x, acc);
    }
    void pop() {
        assert(st1.size() > 1 || st2.size() > 1);
        if (st1.size() > 1) {
            st1.pop();
        } else {
            while (st2.size() > 2) {
                T acc = op(st1.top().second, st2.top().first);
                st1.emplace(st2.top().first, acc);
                st2.pop();
            }
            st2.pop();
        }
    }
    T fold_all() { return op(st1.top().second, st2.top().second); }
};
template <class T, class F> auto make_swag(F op, T e_) { return SlidingWindowAggregation<T, F>(op, e_); }

#line 1 "src/DataStructure/SlidingWindowAggregation.hpp"
/// @docs src/DataStructure/SlidingWindowAggregation.md
template <class T, class F> struct SlidingWindowAggregation {
    const F op;
    const T e;
    std::stack<std::pair<T, T>> st1, st2;  // それぞれ、{val, acc}を要素に持つような前方向と後ろ方向のstack
    SlidingWindowAggregation(F op_, T e_) : op(op_), e(e_) { st1.emplace(e, e), st2.emplace(e, e); }
    int size() { return st1.size() + st2.size() - 2; }
    void push(T x) {
        T acc = op(st2.top().second, x);
        st2.emplace(x, acc);
    }
    void pop() {
        assert(st1.size() > 1 || st2.size() > 1);
        if (st1.size() > 1) {
            st1.pop();
        } else {
            while (st2.size() > 2) {
                T acc = op(st1.top().second, st2.top().first);
                st1.emplace(st2.top().first, acc);
                st2.pop();
            }
            st2.pop();
        }
    }
    T fold_all() { return op(st1.top().second, st2.top().second); }
};
template <class T, class F> auto make_swag(F op, T e_) { return SlidingWindowAggregation<T, F>(op, e_); }

Back to top page