Foldable Queue
(data-structure/foldable-queue.hpp)

• View this file on GitHub
• Last update: 2026-07-11 03:59:32+09:00
• Include: #include "data-structure/foldable-queue.hpp"

列を queue として管理し，列全体の積を取得するデータ構造．

M は Monoid で，列 $A=(A_0,A_1,\dots,A_{N-1})$ に対して all_prod() は $A_0A_1\cdots A_{N-1}$ を返す．空列では M::e() を返す． M::e() は空列に対する all_prod() の返り値としてのみ用いられるため，単位元が存在しない場合も適当な値を定めればよい．

• push(x)：末尾に $x$ を追加する．
• pop()：先頭の要素を削除する．
• size()：要素数を返す．
• empty()：空かどうかを返す．
• all_prod()：列全体の積を返す．

計算量

各操作は償却 $O(1)$．

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp

Verified with

• verify/data-structure/LC_queue_operate_all_composite.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct FoldableQueue {
  using T = typename M::value_type;

  queue<T> front_prod;
  vector<T> back_val;
  T back_prod;
  void push(const T& v) {
    back_prod = back_val.empty() ? v : M::op(back_prod, v);
    back_val.push_back(v);
  }
  void pop() {
    if (front_prod.empty()) {
      for (int i = (int)back_val.size() - 1; i > 0; i--)
        back_val[i - 1] = M::op(back_val[i - 1], back_val[i]);
      for (int i = 0; i < (int)back_val.size(); i++)
        front_prod.push(back_val[i]);
      back_val.clear();
    }
    front_prod.pop();
  }
  size_t size() const { return front_prod.size() + back_val.size(); }
  bool empty() const { return front_prod.empty() && back_val.empty(); }
  T all_prod() const {
    if (front_prod.empty() && back_val.empty()) return M::e();
    if (front_prod.empty()) return back_prod;
    if (back_val.empty()) return front_prod.front();
    return M::op(front_prod.front(), back_prod);
  }
};

/**
 * @brief Foldable Queue
 * @docs docs/data-structure/foldable-queue.md
 */

#line 2 "data-structure/foldable-queue.hpp"

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 4 "data-structure/foldable-queue.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct FoldableQueue {
  using T = typename M::value_type;

  queue<T> front_prod;
  vector<T> back_val;
  T back_prod;
  void push(const T& v) {
    back_prod = back_val.empty() ? v : M::op(back_prod, v);
    back_val.push_back(v);
  }
  void pop() {
    if (front_prod.empty()) {
      for (int i = (int)back_val.size() - 1; i > 0; i--)
        back_val[i - 1] = M::op(back_val[i - 1], back_val[i]);
      for (int i = 0; i < (int)back_val.size(); i++)
        front_prod.push(back_val[i]);
      back_val.clear();
    }
    front_prod.pop();
  }
  size_t size() const { return front_prod.size() + back_val.size(); }
  bool empty() const { return front_prod.empty() && back_val.empty(); }
  T all_prod() const {
    if (front_prod.empty() && back_val.empty()) return M::e();
    if (front_prod.empty()) return back_prod;
    if (back_val.empty()) return front_prod.front();
    return M::op(front_prod.front(), back_prod);
  }
};

/**
 * @brief Foldable Queue
 * @docs docs/data-structure/foldable-queue.md
 */

Back to top page