ds/sliding_window_aggregation.hpp

• View this file on GitHub
• Last update: 2024-11-01 21:56:32+09:00
• Include: #include "ds/sliding_window_aggregation.hpp"

Required by

• poly/from_log_differentiation.hpp
• poly/lagrange_interpolate_iota.hpp
• poly/prefix_product_of_poly.hpp
• poly/sparse_exp_of_div.hpp
• poly/sum_of_C_negative.hpp
• seq/interpolate_poly_exp_sum.hpp
• seq/kth_term_of_p_recursive.hpp

Verified with

• test/1_mytest/factorial_998.test.cpp
• test/2_library_checker/data_structure/deque_operate_all_compsite.test.cpp
• test/2_library_checker/data_structure/queue_operate_all_composite.test.cpp
• test/2_library_checker/enumerative_combinatorics/factorial.test.cpp
• test/2_library_checker/other/sum_of_exp_times_poly.test.cpp
• test/2_library_checker/polynomial/shift_of_sampling_points_of_polynomial.test.cpp
• test/3_yukicoder/1036_3.test.cpp
• test/3_yukicoder/1080_2.test.cpp
• test/3_yukicoder/1117.test.cpp
• test/3_yukicoder/1435_2.test.cpp
• test/3_yukicoder/2026.test.cpp
• test/3_yukicoder/2166.test.cpp
• test/3_yukicoder/2747.test.cpp
• test/3_yukicoder/502_2.test.cpp

Code

template <class Monoid>
struct Sliding_Window_Aggregation {
  using X = typename Monoid::value_type;
  using value_type = X;
  int sz = 0;
  vc<X> dat;
  vc<X> cum_l;
  X cum_r;

  Sliding_Window_Aggregation() : cum_l({Monoid::unit()}), cum_r(Monoid::unit()) {}

  int size() { return sz; }

  void push(X x) {
    ++sz;
    cum_r = Monoid::op(cum_r, x);
    dat.eb(x);
  }

  void pop() {
    --sz;
    cum_l.pop_back();
    if (len(cum_l) == 0) {
      cum_l = {Monoid::unit()};
      cum_r = Monoid::unit();
      while (len(dat) > 1) {
        cum_l.eb(Monoid::op(dat.back(), cum_l.back()));
        dat.pop_back();
      }
      dat.pop_back();
    }
  }

  X lprod() { return cum_l.back(); }
  X rprod() { return cum_r; }

  X prod() { return Monoid::op(cum_l.back(), cum_r); }
};

// 定数倍は目に見えて遅くなるので、queue でよいときは使わない
template <class Monoid>
struct SWAG_deque {
  using X = typename Monoid::value_type;
  using value_type = X;
  int sz;
  vc<X> dat_l, dat_r;
  vc<X> cum_l, cum_r;

  SWAG_deque() : sz(0), cum_l({Monoid::unit()}), cum_r({Monoid::unit()}) {}

  int size() { return sz; }

  void push_back(X x) {
    ++sz;
    dat_r.eb(x);
    cum_r.eb(Monoid::op(cum_r.back(), x));
  }

  void push_front(X x) {
    ++sz;
    dat_l.eb(x);
    cum_l.eb(Monoid::op(x, cum_l.back()));
  }

  void push(X x) { push_back(x); }

  void clear() {
    sz = 0;
    dat_l.clear(), dat_r.clear();
    cum_l = {Monoid::unit()}, cum_r = {Monoid::unit()};
  }

  void pop_front() {
    if (sz == 1) return clear();
    if (dat_l.empty()) rebuild();
    --sz;
    dat_l.pop_back();
    cum_l.pop_back();
  }

  void pop_back() {
    if (sz == 1) return clear();
    if (dat_r.empty()) rebuild();
    --sz;
    dat_r.pop_back();
    cum_r.pop_back();
  }

  void pop() { pop_front(); }

  X front() {
    if (len(dat_l)) return dat_l.back();
    return dat_r[0];
  }

  X lprod() { return cum_l.back(); }
  X rprod() { return cum_r.back(); }
  X prod() { return Monoid::op(cum_l.back(), cum_r.back()); }
  X prod_all() { return prod(); }

private:
  void rebuild() {
    vc<X> X;
    reverse(all(dat_l));
    concat(X, dat_l, dat_r);
    clear();
    int m = len(X) / 2;
    FOR_R(i, m) push_front(X[i]);
    FOR(i, m, len(X)) push_back(X[i]);
    assert(sz == len(X));
  }
};

#line 1 "ds/sliding_window_aggregation.hpp"
template <class Monoid>
struct Sliding_Window_Aggregation {
  using X = typename Monoid::value_type;
  using value_type = X;
  int sz = 0;
  vc<X> dat;
  vc<X> cum_l;
  X cum_r;

  Sliding_Window_Aggregation() : cum_l({Monoid::unit()}), cum_r(Monoid::unit()) {}

  int size() { return sz; }

  void push(X x) {
    ++sz;
    cum_r = Monoid::op(cum_r, x);
    dat.eb(x);
  }

  void pop() {
    --sz;
    cum_l.pop_back();
    if (len(cum_l) == 0) {
      cum_l = {Monoid::unit()};
      cum_r = Monoid::unit();
      while (len(dat) > 1) {
        cum_l.eb(Monoid::op(dat.back(), cum_l.back()));
        dat.pop_back();
      }
      dat.pop_back();
    }
  }

  X lprod() { return cum_l.back(); }
  X rprod() { return cum_r; }

  X prod() { return Monoid::op(cum_l.back(), cum_r); }
};

// 定数倍は目に見えて遅くなるので、queue でよいときは使わない
template <class Monoid>
struct SWAG_deque {
  using X = typename Monoid::value_type;
  using value_type = X;
  int sz;
  vc<X> dat_l, dat_r;
  vc<X> cum_l, cum_r;

  SWAG_deque() : sz(0), cum_l({Monoid::unit()}), cum_r({Monoid::unit()}) {}

  int size() { return sz; }

  void push_back(X x) {
    ++sz;
    dat_r.eb(x);
    cum_r.eb(Monoid::op(cum_r.back(), x));
  }

  void push_front(X x) {
    ++sz;
    dat_l.eb(x);
    cum_l.eb(Monoid::op(x, cum_l.back()));
  }

  void push(X x) { push_back(x); }

  void clear() {
    sz = 0;
    dat_l.clear(), dat_r.clear();
    cum_l = {Monoid::unit()}, cum_r = {Monoid::unit()};
  }

  void pop_front() {
    if (sz == 1) return clear();
    if (dat_l.empty()) rebuild();
    --sz;
    dat_l.pop_back();
    cum_l.pop_back();
  }

  void pop_back() {
    if (sz == 1) return clear();
    if (dat_r.empty()) rebuild();
    --sz;
    dat_r.pop_back();
    cum_r.pop_back();
  }

  void pop() { pop_front(); }

  X front() {
    if (len(dat_l)) return dat_l.back();
    return dat_r[0];
  }

  X lprod() { return cum_l.back(); }
  X rprod() { return cum_r.back(); }
  X prod() { return Monoid::op(cum_l.back(), cum_r.back()); }
  X prod_all() { return prod(); }

private:
  void rebuild() {
    vc<X> X;
    reverse(all(dat_l));
    concat(X, dat_l, dat_r);
    clear();
    int m = len(X) / 2;
    FOR_R(i, m) push_front(X[i]);
    FOR(i, m, len(X)) push_back(X[i]);
    assert(sz == len(X));
  }
};

Back to top page