Sliding Window Aggregation (lib/data_structure/swag.hpp)

View this file on GitHub
Last update: 2026-03-15 03:14:58+09:00
Include: #include "lib/data_structure/swag.hpp"

Depends on

lib/segtree/monoid.hpp

Verified with

Code

#pragma once
#include <stack>
#include "segtree/monoid.hpp"

/// @brief Sliding Window Aggregation
template <class M>
struct sliding_window_aggregation {
  private:
    using T = typename M::value_type;

  public:
    sliding_window_aggregation() : back_total(M::id()), front(), back() { front.emplace(M::id()); }

    bool empty() const { return front.empty() && back.empty(); }
    int size() const { return front.size() + back.size() - 1; }

    T fold() const { return M::op(back_total, front.top()); }

    void emplace(T val) {
        back.emplace(val);
        back_total = M::op(val, back_total);
    }
    void push(T val) { emplace(val); }

    void pop() {
        if (front.size() == 1) {
            while (!back.empty()) {
                front.emplace(M::op(front.top(), back.top()));
                back.pop();
            }
            back_total = M::id();
        }
        front.pop();
    }

  private:
    T back_total;
    std::stack<T> front, back;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: segtree/monoid.hpp: line -1: no such header