sliding_window_aggregation.hpp¶
队尾加入、队首删除，并查询整个窗口合并后的信息；例如窗口最值或依次复合函数。合并须满足结合律，增删均摊 \(O(1)\)，整窗查询 \(O(1)\)。
Complexity: Time: \(O(n + k)\) build replacing \(k\) elements; amortized \(O(1)\) push/pop and \(O(1)\) product. Space: \(O(w + 1)\) value slots, \(w\) = largest window size so far.
Source: maspy
AC 记录：queue_operate_all_composite。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n+k) build replacing k elements; amortized O(1) push/pop
/// and O(1) product. Space: O(w+1) value slots, w = largest window size so far.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Queue aggregation for an associative Monoid with value_type, unit(),
/// and op(l, r). Products preserve queue order; commutativity is not required.
/// Bounds assume constant-time value operations; clear/build reuse capacity.
template <class Monoid> struct swag {
using MX = Monoid;
using value_type = typename MX::value_type;
using S = value_type;
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() : sl{MX::unit()}, sr(MX::unit()) {}
explicit swag(const std::vector<S> &a) : swag() { build(a); }
void clear() {
sz = 0;
dat.clear();
sl = {MX::unit()};
sr = MX::unit();
}
void build(const std::vector<S> &a) {
clear();
dat = a;
sz = int(dat.size());
for (const S &x : dat) sr = MX::op(sr, x);
}
int size() const { return sz; }
bool empty() const { return sz == 0; }
/// @brief Push element x to the back of the window.
void push_back(S x) {
++sz;
sr = MX::op(sr, x);
dat.push_back(std::move(x));
}
/// @brief Pop the front element from the window.
void pop_front() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {MX::unit()};
sr = MX::unit();
while ((int)dat.size() > 1) {
sl.push_back(MX::op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
// Compatibility names used by existing contest solutions.
void push(S x) { push_back(std::move(x)); }
void pop() { pop_front(); }
S lprod() const { return sl.back(); }
S rprod() const { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S all_prod() const { return MX::op(sl.back(), sr); }
S prod() const { return all_prod(); }
};
} // namespace noya
// NOYA_SLIDING_WINDOW_AGGREGATION_HPP
#ifndef NOYA_SLIDING_WINDOW_AGGREGATION_HPP
#define NOYA_SLIDING_WINDOW_AGGREGATION_HPP 1
/// @complexity Time: O(n+k) build replacing k elements; amortized O(1) push/pop
/// and O(1) product. Space: O(w+1) value slots, w = largest window size so far.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Queue aggregation for an associative Monoid with value_type, unit(),
/// and op(l, r). Products preserve queue order; commutativity is not required.
/// Bounds assume constant-time value operations; clear/build reuse capacity.
template <class Monoid> struct swag {
using MX = Monoid;
using value_type = typename MX::value_type;
using S = value_type;
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() : sl{MX::unit()}, sr(MX::unit()) {}
explicit swag(const std::vector<S> &a) : swag() { build(a); }
void clear() {
sz = 0;
dat.clear();
sl = {MX::unit()};
sr = MX::unit();
}
void build(const std::vector<S> &a) {
clear();
dat = a;
sz = int(dat.size());
for (const S &x : dat) sr = MX::op(sr, x);
}
int size() const { return sz; }
bool empty() const { return sz == 0; }
/// @brief Push element x to the back of the window.
void push_back(S x) {
++sz;
sr = MX::op(sr, x);
dat.push_back(std::move(x));
}
/// @brief Pop the front element from the window.
void pop_front() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {MX::unit()};
sr = MX::unit();
while ((int)dat.size() > 1) {
sl.push_back(MX::op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
// Compatibility names used by existing contest solutions.
void push(S x) { push_back(std::move(x)); }
void pop() { pop_front(); }
S lprod() const { return sl.back(); }
S rprod() const { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S all_prod() const { return MX::op(sl.back(), sr); }
S prod() const { return all_prod(); }
};
} // namespace noya
#endif // NOYA_SLIDING_WINDOW_AGGREGATION_HPP
/// @complexity Time: O(n+k) build replacing k elements; amortized O(1) push/pop
/// and O(1) product. Space: O(w+1) value slots, w = largest window size so far.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Queue aggregation for an associative Monoid with value_type, unit(),
/// and op(l, r). Products preserve queue order; commutativity is not required.
/// Bounds assume constant-time value operations; clear/build reuse capacity.
template <class Monoid> struct swag {
using MX = Monoid;
using value_type = typename MX::value_type;
using S = value_type;
int sz = 0;
std::vector<S> dat;
std::vector<S> sl;
S sr;
swag() : sl{MX::unit()}, sr(MX::unit()) {}
explicit swag(const std::vector<S> &a) : swag() { build(a); }
void clear() {
sz = 0;
dat.clear();
sl = {MX::unit()};
sr = MX::unit();
}
void build(const std::vector<S> &a) {
clear();
dat = a;
sz = int(dat.size());
for (const S &x : dat) sr = MX::op(sr, x);
}
int size() const { return sz; }
bool empty() const { return sz == 0; }
/// @brief Push element x to the back of the window.
void push_back(S x) {
++sz;
sr = MX::op(sr, x);
dat.push_back(std::move(x));
}
/// @brief Pop the front element from the window.
void pop_front() {
assert(0 < sz);
--sz;
sl.pop_back();
if ((int)sl.size() == 0) {
sl = {MX::unit()};
sr = MX::unit();
while ((int)dat.size() > 1) {
sl.push_back(MX::op(dat.back(), sl.back()));
dat.pop_back();
}
dat.pop_back();
}
}
// Compatibility names used by existing contest solutions.
void push(S x) { push_back(std::move(x)); }
void pop() { pop_front(); }
S lprod() const { return sl.back(); }
S rprod() const { return sr; }
/// @brief Return the aggregate product of all elements in the window.
S all_prod() const { return MX::op(sl.back(), sr); }
S prod() const { return all_prod(); }
};
} // namespace noya
// NOYA_SLIDING_WINDOW_AGGREGATION_HPP