sliding_window_aggregation.hpp¶

SECTIONData Structure INCLUDEnoya/ds/sliding_window_aggregation.hpp

用两个栈维护队列中所有元素的可结合乘积；适合滑动窗口内求和、最值或函数复合。

Complexity: Time: O(n) build; amortized O(1) push/pop and O(1) product. Space: O(n) window elements.

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n) build; amortized O(1) push/pop and O(1) product.
/// Space: O(n) window elements.

#include <algorithm>
#include <cassert>
#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.
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();
    for (const S &x : a) push_back(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(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(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) build; amortized O(1) push/pop and O(1) product.
/// Space: O(n) window elements.

#include <algorithm>
#include <cassert>
#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.
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();
    for (const S &x : a) push_back(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(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(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) build; amortized O(1) push/pop and O(1) product.
/// Space: O(n) window elements.

#include <algorithm>
#include <cassert>
#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.
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();
    for (const S &x : a) push_back(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(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(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