Sliding Window Aggregation
(src/datastructure/SlidingWindowAggregation.hpp)

• View this file on GitHub
• Last update: 2024-05-21 23:41:26+09:00
• Include: #include "src/datastructure/SlidingWindowAggregation.hpp"

概要

問題例

• yukicoder No.2215 Slide Subset Sum

Verified with

• test/yosupo/queue_operate_all_composite.test.cpp

Code

#pragma once
#include <functional>
#include <stack>

template <class S, S (*op)(S, S), S (*e)()> struct SlidingWindowAggregation {
    std::stack<std::pair<S, S>> front_stack, back_stack;
    SlidingWindowAggregation() : front_stack(), back_stack() {
        front_stack.emplace(e(), e());
        back_stack.emplace(e(), e());
    }
    void push(const S& x) { back_stack.emplace(x, op(back_stack.top().second, x)); }
    void pop() {
        if (front_stack.size() == 1) {
            while (1 < (int)back_stack.size()) {
                S t = back_stack.top().first;
                S calc = op(t, front_stack.top().second);
                front_stack.emplace(t, calc);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
    S fold() { return op(front_stack.top().second, back_stack.top().second); }
};

#line 2 "src/datastructure/SlidingWindowAggregation.hpp"
#include <functional>
#include <stack>

template <class S, S (*op)(S, S), S (*e)()> struct SlidingWindowAggregation {
    std::stack<std::pair<S, S>> front_stack, back_stack;
    SlidingWindowAggregation() : front_stack(), back_stack() {
        front_stack.emplace(e(), e());
        back_stack.emplace(e(), e());
    }
    void push(const S& x) { back_stack.emplace(x, op(back_stack.top().second, x)); }
    void pop() {
        if (front_stack.size() == 1) {
            while (1 < (int)back_stack.size()) {
                S t = back_stack.top().first;
                S calc = op(t, front_stack.top().second);
                front_stack.emplace(t, calc);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
    S fold() { return op(front_stack.top().second, back_stack.top().second); }
};

Back to top page