Deque Operate Aggregation (structure/others/deque-operate-aggregation.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-07-15 03:25:28+09:00
• Include: #include "structure/others/deque-operate-aggregation.hpp"

半群の要素列 $A$ に対して以下の操作を効率的に行います。

• push_front: $A$ の先頭に要素を追加する
• pop_front: $A$ の先頭の要素を削除する
• push_back: $A$ の末尾に要素を追加する
• pop_back: $A$ の末尾の要素を削除する
• all_prod: $A$ 全体の集約値の取得する

コンストラクタ

DequeOperateAggregation< T, F >(F f)

二項演算 $f$ で定義される型 T の半群の要素列 $A$ を、空の列で初期化します。

計算量

• $O(1)$

empty

bool empty() const

$A$ が空のとき true、空でないとき false を返します。

計算量

• $O(1)$

size

size_t size() const

$A$ の要素数を返します。

計算量

• $O(1)$

all_prod

T all_prod() const

$A$ 全体を $f$ で集約した値を返します。

制約

• $A$ が空ではない

計算量

• $O(1)$

push_front

void push_front(const T &x)

$A$ の先頭に $x$ を追加します。

計算量

• $O(1)$

push_back

void push_back(const T& x)

$A$ の末尾に $x$ を追加します。

計算量

• $O(1)$

pop_front

void pop_front()

$A$ の先頭の要素を削除します。

制約

• $A$ が空ではない

計算量

• amortized $O(1)$

pop_back

void pop_back()

$A$ の末尾の要素を削除します。

制約

• $A$ が空ではない

計算量

• amortized $O(1)$

get_deque_operate_aggregation

template<typename T, typename F>
DequeOperateAggregation<T, F> get_deque_operate_aggregation(const F &f)

型 T、二項演算 f の半群に対応する DequeOperateAggregation を返すヘルパー関数です。

計算量

• $O(1)$

使用例

auto deque = get_deque_operate_aggregation< T >(f);

Verified with

• test/verify/yosupo-deque-operate-all-composite.test.cpp

Code

template <typename T, typename F>
struct DequeOperateAggregation {
 private:
  struct Node {
    T val, sum;

    Node(const T &val, const T &sum) : val(val), sum(sum) {}
  };
  const F f;
  vector<Node> st[2];

  void rebuild() {
    if (not st[0].empty()) {
      st[0][0].sum = st[0][0].val;
      for (int i = 1; i < (int)st[0].size(); i++) {
        st[0][i].sum = f(st[0][i].val, st[0][i - 1].sum);
      }
    }
    if (not st[1].empty()) {
      st[1][0].sum = st[1][0].val;
      for (int i = 1; i < (int)st[1].size(); i++) {
        st[1][i].sum = f(st[1][i - 1].sum, st[1][i].val);
      }
    }
  }

 public:
  DequeOperateAggregation() = default;

  explicit DequeOperateAggregation(F f) : f(f) {}

  bool empty() const { return st[0].empty() and st[1].empty(); }

  size_t size() const { return st[0].size() + st[1].size(); }

  T all_prod() const {
    assert(not empty());
    if (st[0].empty()) {
      return st[1].back().sum;
    } else if (st[1].empty()) {
      return st[0].back().sum;
    } else {
      return f(st[0].back().sum, st[1].back().sum);
    }
  }

  void push_front(const T &x) {
    if (st[0].empty()) {
      st[0].emplace_back(x, x);
    } else {
      st[0].emplace_back(x, f(x, st[0].back().sum));
    }
  }

  void push_back(const T &x) {
    if (st[1].empty()) {
      st[1].emplace_back(x, x);
    } else {
      st[1].emplace_back(x, f(st[1].back().sum, x));
    }
  }

  void pop_front() {
    assert(not empty());
    if (st[0].empty()) {
      auto m = st[1].size() / 2;
      st[0] = {st[1].rbegin() + m, st[1].rend()};
      st[1] = {st[1].end() - m, st[1].end()};
      rebuild();
    }
    st[0].pop_back();
  }

  void pop_back() {
    assert(not empty());
    if (st[1].empty()) {
      auto m = st[0].size() / 2;
      st[1] = {st[0].rbegin() + m, st[0].rend()};
      st[0] = {st[0].end() - m, st[0].end()};
      rebuild();
    }
    st[1].pop_back();
  }
};

template <typename T, typename F>
DequeOperateAggregation<T, F> get_deque_operate_aggregation(const F &f) {
  return DequeOperateAggregation<T, F>{f};
}

#line 1 "structure/others/deque-operate-aggregation.hpp"
template <typename T, typename F>
struct DequeOperateAggregation {
 private:
  struct Node {
    T val, sum;

    Node(const T &val, const T &sum) : val(val), sum(sum) {}
  };
  const F f;
  vector<Node> st[2];

  void rebuild() {
    if (not st[0].empty()) {
      st[0][0].sum = st[0][0].val;
      for (int i = 1; i < (int)st[0].size(); i++) {
        st[0][i].sum = f(st[0][i].val, st[0][i - 1].sum);
      }
    }
    if (not st[1].empty()) {
      st[1][0].sum = st[1][0].val;
      for (int i = 1; i < (int)st[1].size(); i++) {
        st[1][i].sum = f(st[1][i - 1].sum, st[1][i].val);
      }
    }
  }

 public:
  DequeOperateAggregation() = default;

  explicit DequeOperateAggregation(F f) : f(f) {}

  bool empty() const { return st[0].empty() and st[1].empty(); }

  size_t size() const { return st[0].size() + st[1].size(); }

  T all_prod() const {
    assert(not empty());
    if (st[0].empty()) {
      return st[1].back().sum;
    } else if (st[1].empty()) {
      return st[0].back().sum;
    } else {
      return f(st[0].back().sum, st[1].back().sum);
    }
  }

  void push_front(const T &x) {
    if (st[0].empty()) {
      st[0].emplace_back(x, x);
    } else {
      st[0].emplace_back(x, f(x, st[0].back().sum));
    }
  }

  void push_back(const T &x) {
    if (st[1].empty()) {
      st[1].emplace_back(x, x);
    } else {
      st[1].emplace_back(x, f(st[1].back().sum, x));
    }
  }

  void pop_front() {
    assert(not empty());
    if (st[0].empty()) {
      auto m = st[1].size() / 2;
      st[0] = {st[1].rbegin() + m, st[1].rend()};
      st[1] = {st[1].end() - m, st[1].end()};
      rebuild();
    }
    st[0].pop_back();
  }

  void pop_back() {
    assert(not empty());
    if (st[1].empty()) {
      auto m = st[0].size() / 2;
      st[1] = {st[0].rbegin() + m, st[0].rend()};
      st[0] = {st[0].end() - m, st[0].end()};
      rebuild();
    }
    st[1].pop_back();
  }
};

template <typename T, typename F>
DequeOperateAggregation<T, F> get_deque_operate_aggregation(const F &f) {
  return DequeOperateAggregation<T, F>{f};
}

Back to top page