Foldable Deque
(data-structure/foldable-deque.hpp)

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

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

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_front(x)：先頭に $x$ を追加する．
• push_back(x)：末尾に $x$ を追加する．
• pop_front()：先頭の要素を削除する．
• pop_back()：末尾の要素を削除する．
• front()：先頭の要素を返す．
• back()：末尾の要素を返す．
• 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_deque_operate_all_composite.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"

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

 private:
  struct Node {
    T val, prod;
  };
  vector<Node> front_stack, back_stack;
  void push_front_stack(const T& v) {
    T prod = front_stack.empty() ? v : M::op(v, front_stack.back().prod);
    front_stack.push_back({v, prod});
  }
  void push_back_stack(const T& v) {
    T prod = back_stack.empty() ? v : M::op(back_stack.back().prod, v);
    back_stack.push_back({v, prod});
  }
  void rebuild_front() {
    int n = back_stack.size();
    int k = (n + 1) / 2;
    vector<T> a(n);
    for (int i = 0; i < n; i++) a[i] = back_stack[i].val;
    front_stack.clear();
    back_stack.clear();
    for (int i = k - 1; i >= 0; i--) push_front_stack(a[i]);
    for (int i = k; i < n; i++) push_back_stack(a[i]);
  }
  void rebuild_back() {
    int n = front_stack.size();
    int k = (n + 1) / 2;
    vector<T> a(n);
    for (int i = 0; i < n; i++) a[i] = front_stack[n - 1 - i].val;
    front_stack.clear();
    back_stack.clear();
    for (int i = 0; i < n - k; i++) push_front_stack(a[n - k - 1 - i]);
    for (int i = n - k; i < n; i++) push_back_stack(a[i]);
  }

 public:
  FoldableDeque() {}

  size_t size() const { return front_stack.size() + back_stack.size(); }
  bool empty() const { return front_stack.empty() && back_stack.empty(); }
  void push_front(const T& v) { push_front_stack(v); }
  void push_back(const T& v) { push_back_stack(v); }
  void pop_front() {
    if (front_stack.empty()) rebuild_front();
    front_stack.pop_back();
  }
  void pop_back() {
    if (back_stack.empty()) rebuild_back();
    back_stack.pop_back();
  }
  const T& front() {
    if (front_stack.empty()) rebuild_front();
    return front_stack.back().val;
  }
  const T& back() {
    if (back_stack.empty()) rebuild_back();
    return back_stack.back().val;
  }
  T all_prod() const {
    if (front_stack.empty() && back_stack.empty()) return M::e();
    if (front_stack.empty()) return back_stack.back().prod;
    if (back_stack.empty()) return front_stack.back().prod;
    return M::op(front_stack.back().prod, back_stack.back().prod);
  }
};

/**
 * @brief Foldable Deque
 * @docs docs/data-structure/foldable-deque.md
 */

#line 2 "data-structure/foldable-deque.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-deque.hpp"

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

 private:
  struct Node {
    T val, prod;
  };
  vector<Node> front_stack, back_stack;
  void push_front_stack(const T& v) {
    T prod = front_stack.empty() ? v : M::op(v, front_stack.back().prod);
    front_stack.push_back({v, prod});
  }
  void push_back_stack(const T& v) {
    T prod = back_stack.empty() ? v : M::op(back_stack.back().prod, v);
    back_stack.push_back({v, prod});
  }
  void rebuild_front() {
    int n = back_stack.size();
    int k = (n + 1) / 2;
    vector<T> a(n);
    for (int i = 0; i < n; i++) a[i] = back_stack[i].val;
    front_stack.clear();
    back_stack.clear();
    for (int i = k - 1; i >= 0; i--) push_front_stack(a[i]);
    for (int i = k; i < n; i++) push_back_stack(a[i]);
  }
  void rebuild_back() {
    int n = front_stack.size();
    int k = (n + 1) / 2;
    vector<T> a(n);
    for (int i = 0; i < n; i++) a[i] = front_stack[n - 1 - i].val;
    front_stack.clear();
    back_stack.clear();
    for (int i = 0; i < n - k; i++) push_front_stack(a[n - k - 1 - i]);
    for (int i = n - k; i < n; i++) push_back_stack(a[i]);
  }

 public:
  FoldableDeque() {}

  size_t size() const { return front_stack.size() + back_stack.size(); }
  bool empty() const { return front_stack.empty() && back_stack.empty(); }
  void push_front(const T& v) { push_front_stack(v); }
  void push_back(const T& v) { push_back_stack(v); }
  void pop_front() {
    if (front_stack.empty()) rebuild_front();
    front_stack.pop_back();
  }
  void pop_back() {
    if (back_stack.empty()) rebuild_back();
    back_stack.pop_back();
  }
  const T& front() {
    if (front_stack.empty()) rebuild_front();
    return front_stack.back().val;
  }
  const T& back() {
    if (back_stack.empty()) rebuild_back();
    return back_stack.back().val;
  }
  T all_prod() const {
    if (front_stack.empty() && back_stack.empty()) return M::e();
    if (front_stack.empty()) return back_stack.back().prod;
    if (back_stack.empty()) return front_stack.back().prod;
    return M::op(front_stack.back().prod, back_stack.back().prod);
  }
};

/**
 * @brief Foldable Deque
 * @docs docs/data-structure/foldable-deque.md
 */

Back to top page