sliding_window_aggregation.hpp¶
用两个栈维护队列中所有元素的可结合乘积；适合滑动窗口内求和、最值或函数复合。
Complexity: Time: Amortized O(1) push/pop/product. Space: O(n) window elements.
AC 记录：queue_operate_all_composite。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(1) push/pop/product.
/// Space: O(n) window elements.
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
namespace noya {
#if __cplusplus >= 201703L
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, auto op, auto e> struct swag {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, S (*op)(S, S), S (*e)()> struct swag {
#endif
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() {
sl = {e()};
sr = e();
}
int size() { return sz; }
/// @brief Push element x to the back of the window.
void push(S x) {
++sz;
sr = op(sr, x);
dat.push_back(x);
}
/// @brief Pop the front element from the window.
void pop() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {e()};
sr = e();
while ((int)dat.size() > 1) {
sl.push_back(op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
S lprod() { return sl.back(); }
S rprod() { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S prod() { return op(sl.back(), sr); }
};
} // namespace noya
#ifndef NOYA_SLIDING_WINDOW_AGGREGATION_HPP
#define NOYA_SLIDING_WINDOW_AGGREGATION_HPP 1
/// @complexity Time: Amortized O(1) push/pop/product.
/// Space: O(n) window elements.
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
namespace noya {
#if __cplusplus >= 201703L
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, auto op, auto e> struct swag {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, S (*op)(S, S), S (*e)()> struct swag {
#endif
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() {
sl = {e()};
sr = e();
}
int size() { return sz; }
/// @brief Push element x to the back of the window.
void push(S x) {
++sz;
sr = op(sr, x);
dat.push_back(x);
}
/// @brief Pop the front element from the window.
void pop() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {e()};
sr = e();
while ((int)dat.size() > 1) {
sl.push_back(op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
S lprod() { return sl.back(); }
S rprod() { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S prod() { return op(sl.back(), sr); }
};
} // namespace noya
#endif // NOYA_SLIDING_WINDOW_AGGREGATION_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
/// @complexity Time: Amortized O(1) push/pop/product.
/// Space: O(n) window elements.
namespace noya {
#if __cplusplus >= 201703L
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, auto op, auto e> struct swag {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, S (*op)(S, S), S (*e)()> struct swag {
#endif
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() {
sl = {e()};
sr = e();
}
int size() { return sz; }
/// @brief Push element x to the back of the window.
void push(S x) {
++sz;
sr = op(sr, x);
dat.push_back(x);
}
/// @brief Pop the front element from the window.
void pop() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {e()};
sr = e();
while ((int)dat.size() > 1) {
sl.push_back(op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
S lprod() { return sl.back(); }
S rprod() { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S prod() { return op(sl.back(), sr); }
};
} // namespace noya