Queue Operate Aggregation (structure/others/queue-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/queue-operate-aggregation.hpp"

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

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

コンストラクタ

QueueOperateAggregation< 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

void push(const T &x)

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

計算量

• $O(1)$

pop

void pop()

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

制約

• $A$ が空ではない

計算量

• amortized $O(1)$

get_queue_operate_aggregation

template<typename T, typename F>
QueueOperateAggregation<T, F> get_queue_operate_aggregation(const F &f)

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

計算量

• $O(1)$

使用例

auto que = get_queue_operate_aggregation< T >(f);

Verified with

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

Code

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

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

 public:
  QueueOperateAggregation() = default;

  explicit QueueOperateAggregation(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(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() {
    assert(not empty());
    if (st[0].empty()) {
      st[0].emplace_back(st[1].back().val, st[1].back().val);
      st[1].pop_back();
      while (not st[1].empty()) {
        st[0].emplace_back(st[1].back().val,
                           f(st[1].back().val, st[0].back().sum));
        st[1].pop_back();
      }
    }
    st[0].pop_back();
  }
};

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

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

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

 public:
  QueueOperateAggregation() = default;

  explicit QueueOperateAggregation(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(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() {
    assert(not empty());
    if (st[0].empty()) {
      st[0].emplace_back(st[1].back().val, st[1].back().val);
      st[1].pop_back();
      while (not st[1].empty()) {
        st[0].emplace_back(st[1].back().val,
                           f(st[1].back().val, st[0].back().sum));
        st[1].pop_back();
      }
    }
    st[0].pop_back();
  }
};

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

Back to top page