Partially Retroactive Priority Queue (structure/heap/partially-retroactive-priority-queue.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-07-31 08:17:49+00:00
• Include: #include "structure/heap/partially-retroactive-priority-queue.hpp"

長さ $N$ の操作列を持つ優先度付きキューです。各時刻の操作を過去にさかのぼって push、pop、何もしない操作のいずれかへ変更し、操作列を空の優先度付きキューへ適用したあとの状態を管理します。

空の優先度付きキューに対する pop は無視されます。Compare のデフォルトは std::less<T> で、最小値が先に取り除かれます。

Compare によって同順位となる要素が複数ある場合は、より早い時刻に push された要素が先に取り除かれます。

各 push を最終状態に残る要素と途中で取り除かれる要素に分類し、操作列の接頭辞和が $0$ となる境界と、境界の前後で入れ替わる候補をセグメント木で管理します。空のキューに対する pop は、操作列の先頭に、すべての実要素より優先度が低い仮想要素を $N$ 個追加することで通常の pop と同様に扱います。

コンストラクタ

PartiallyRetroactivePriorityQueue<T, Compare>(int n, Compare compare = Compare())

長さ n の操作列を、すべて何もしない操作として初期化します。

制約

• $0 \leq n$
• Compare は狭義弱順序を定める
• T{} は加法単位元を表す
• T は +=、-=、コピー構築、ムーブ構築が可能

計算量

• 時間 $O(n)$
• 空間 $O(n)$

set_push

void set_push(int t, T value)

時刻 t の操作を value の push に変更します。以前の操作は上書きされます。

制約

• $0 \leq t < n$

計算量

• $O(\log n)$

set_pop

void set_pop(int t)

時刻 t の操作を優先要素の pop に変更します。以前の操作は上書きされます。その時点でキューが空なら何も行いません。

制約

• $0 \leq t < n$

計算量

• $O(\log n)$

set_noop

void set_noop(int t)

時刻 t の操作を何もしない操作に変更します。以前の操作は上書きされます。

制約

• $0 \leq t < n$

計算量

• $O(\log n)$

empty

bool empty() const

すべての操作を適用したあとの優先度付きキューが空かを返します。

計算量

• $O(1)$

size

int size() const

すべての操作を適用したあとに残る要素数を返します。

計算量

• $O(1)$

top

const T& top() const

すべての操作を適用したあとに残る優先要素を返します。

制約

• empty() が false

計算量

• $O(1)$

sum

T sum() const

すべての操作を適用したあとに残る全要素の総和を返します。

計算量

• $O(1)$

Depends on

• structure/class/acted-monoid.hpp
• structure/class/range-add-range-min.hpp
• Lazy Segment Tree (遅延伝搬セグメント木) (structure/segment-tree/lazy-segment-tree.hpp)

Verified with

• test/unittest/partially-retroactive-priority-queue.test.cpp

Code

#pragma once

#include "../class/range-add-range-min.hpp"
#include "../segment-tree/lazy-segment-tree.hpp"

template <typename T, typename Compare = std::less<T> >
struct PartiallyRetroactivePriorityQueue {
 private:
  enum class OperationType : uint8_t { NOOP, PUSH, POP };

  struct Operation {
    OperationType type = OperationType::NOOP;
    optional<T> value;
    bool alive = false;
  };

  struct CandidateNode {
    int alive_min = -1;
    int deleted_max = -1;
  };

  int n;
  int operation_count;
  int seg_size;
  Compare compare;

  vector<Operation> operations;
  vector<CandidateNode> candidates;
  // A deleted push has weight +1, a surviving push has weight 0, and a pop
  // has weight -1. Their prefix sums are nonnegative, and a zero is a bridge.
  // Updating one operation is a suffix addition on the prefix-sum array.
  LazySegmentTree<RangeAddRangeMin<int> > prefix;

  // A batch of n virtual values with lower priority than every real value is
  // inserted before the timeline. It makes every pop valid; popping one of
  // them is exactly an ignored pop on an empty real queue.
  int dummy_alive;
  int dummy_deleted = 0;

  int present_size = 0;
  T present_sum{};

  bool key_less(int a, int b) const {
    assert(a >= 0 and b >= 0);
    if (a == b) return false;
    if (a == 0) return false;
    if (b == 0) return true;
    const T& x = *operations[a - 1].value;
    const T& y = *operations[b - 1].value;
    if (compare(x, y)) return true;
    if (compare(y, x)) return false;
    return a < b;
  }

  int min_id(int a, int b) const {
    if (a == -1) return b;
    if (b == -1) return a;
    return key_less(a, b) ? a : b;
  }

  int max_id(int a, int b) const {
    if (a == -1) return b;
    if (b == -1) return a;
    return key_less(a, b) ? b : a;
  }

  void pull_candidate(int k) {
    candidates[k].alive_min =
        min_id(candidates[2 * k].alive_min, candidates[2 * k + 1].alive_min);
    candidates[k].deleted_max = max_id(candidates[2 * k].deleted_max,
                                       candidates[2 * k + 1].deleted_max);
  }

  void refresh_candidate(int p) {
    CandidateNode node;
    if (p == 0) {
      if (dummy_alive > 0) node.alive_min = 0;
      if (dummy_deleted > 0) node.deleted_max = 0;
    } else {
      const auto& op = operations[p - 1];
      if (op.type == OperationType::PUSH) {
        if (op.alive) {
          node.alive_min = p;
        } else {
          node.deleted_max = p;
        }
      }
    }
    int k = p + seg_size;
    candidates[k] = node;
    while (k >>= 1) pull_candidate(k);
  }

  int range_min_alive(int l, int r) const {
    int ret = -1;
    for (l += seg_size, r += seg_size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = min_id(ret, candidates[l++].alive_min);
      if (r & 1) ret = min_id(ret, candidates[--r].alive_min);
    }
    assert(ret != -1);
    return ret;
  }

  int range_max_deleted(int l, int r) const {
    int ret = -1;
    for (l += seg_size, r += seg_size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = max_id(ret, candidates[l++].deleted_max);
      if (r & 1) ret = max_id(ret, candidates[--r].deleted_max);
    }
    assert(ret != -1);
    return ret;
  }

  void add_weight(int p, int x) { prefix.apply(p + 1, operation_count + 1, x); }

  int find_first_zero(int l) {
    auto ret = prefix.find_first(l, [](int x) { return x == 0; });
    assert(ret.has_value());
    return *ret - 1;
  }

  int find_last_zero(int r) {
    auto ret = prefix.find_last(r + 1, [](int x) { return x == 0; });
    assert(ret.has_value());
    return *ret;
  }

  void promote(int id) {
    if (id == 0) {
      assert(dummy_deleted > 0);
      --dummy_deleted;
      ++dummy_alive;
      add_weight(0, -1);
      refresh_candidate(0);
      return;
    }
    auto& op = operations[id - 1];
    assert(op.type == OperationType::PUSH and not op.alive);
    op.alive = true;
    add_weight(id, -1);
    ++present_size;
    present_sum += *op.value;
    refresh_candidate(id);
  }

  void demote(int id) {
    if (id == 0) {
      assert(dummy_alive > 0);
      --dummy_alive;
      ++dummy_deleted;
      add_weight(0, 1);
      refresh_candidate(0);
      return;
    }
    auto& op = operations[id - 1];
    assert(op.type == OperationType::PUSH and op.alive);
    op.alive = false;
    add_weight(id, 1);
    --present_size;
    present_sum -= *op.value;
    refresh_candidate(id);
  }

  void check_time(int t) const { assert(0 <= t and t < n); }

  static int checked_size(int size) {
    assert(size >= 0);
    return size;
  }

 public:
  explicit PartiallyRetroactivePriorityQueue(int size,
                                             Compare comparator = Compare())
      : n(checked_size(size)),
        operation_count(n + 1),
        seg_size(1),
        compare(std::move(comparator)),
        operations(n),
        prefix(RangeAddRangeMin<int>(), vector<int>(n + 2)),
        dummy_alive(n) {
    while (seg_size < operation_count) seg_size <<= 1;
    candidates.assign(2 * seg_size, CandidateNode{});
    refresh_candidate(0);
  }

  /** Replaces operation t by push(value). */
  void set_push(int t, T value) {
    check_time(t);
    set_noop(t);
    int p = t + 1;
    auto& op = operations[t];
    op.type = OperationType::PUSH;
    op.value.emplace(std::move(value));
    op.alive = false;
    add_weight(p, 1);
    refresh_candidate(p);

    int bridge = find_last_zero(p);
    promote(range_max_deleted(bridge, operation_count));
  }

  /** Replaces operation t by pop. It is ignored when the queue is empty. */
  void set_pop(int t) {
    check_time(t);
    set_noop(t);
    int p = t + 1;

    int bridge = find_first_zero(p + 1);
    demote(range_min_alive(0, bridge));

    auto& op = operations[t];
    op.type = OperationType::POP;
    op.value.reset();
    op.alive = false;
    add_weight(p, -1);
  }

  /** Replaces operation t by a no-op. */
  void set_noop(int t) {
    check_time(t);
    int p = t + 1;
    auto& op = operations[t];
    if (op.type == OperationType::NOOP) return;

    if (op.type == OperationType::POP) {
      int bridge = find_last_zero(p);
      int id = range_max_deleted(bridge, operation_count);
      add_weight(p, 1);
      promote(id);
    } else if (op.alive) {
      --present_size;
      present_sum -= *op.value;
    } else {
      int bridge = find_first_zero(p + 1);
      int id = range_min_alive(0, bridge);
      demote(id);
      add_weight(p, -1);
    }

    op.type = OperationType::NOOP;
    op.alive = false;
    refresh_candidate(p);
    op.value.reset();
  }

  bool empty() const { return present_size == 0; }

  int size() const { return present_size; }

  const T& top() const {
    assert(not empty());
    int id = candidates[1].alive_min;
    assert(id > 0);
    return *operations[id - 1].value;
  }

  T sum() const { return present_sum; }
};

#line 2 "structure/heap/partially-retroactive-priority-queue.hpp"

#line 2 "structure/class/range-add-range-min.hpp"

template <typename T>
struct RangeAddRangeMin {
  using S = T;
  using F = T;
  static constexpr S op(const S& a, const S& b) { return min(a, b); }
  static constexpr S e() { return numeric_limits<T>::max(); }
  static constexpr F mapping(const S& x, const F& f) { return x + f; }
  static constexpr F composition(const F& f, const F& g) { return f + g; }
  static constexpr F id() { return {0}; }
};
#line 2 "structure/segment-tree/lazy-segment-tree.hpp"

#line 2 "structure/class/acted-monoid.hpp"

template <typename S2, typename Op, typename E, typename F2, typename Mapping,
          typename Composition, typename Id>
struct LambdaActedMonoid {
  using S = S2;
  using F = F2;

  S op(const S& a, const S& b) const { return _op(a, b); }

  S e() const { return _e(); }

  S mapping(const S& x, const F& f) const { return _mapping(x, f); }

  F composition(const F& f, const F& g) const { return _composition(f, g); }

  F id() const { return _id(); }

  LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition,
                    Id _id)
      : _op(_op),
        _e(_e),
        _mapping(_mapping),
        _composition(_composition),
        _id(_id) {}

 private:
  Op _op;

  E _e;

  Mapping _mapping;

  Composition _composition;

  Id _id;
};

template <typename Op, typename E, typename Mapping, typename Composition,
          typename Id>
LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition,
                  Id _id)
    -> LambdaActedMonoid<decltype(_e()), Op, E, decltype(_id()), Mapping,
                         Composition, Id>;

/*
struct ActedMonoid {
  using S = ?;
  using F = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
  static constexpr S mapping(const S &x, const F &f) {}
  static constexpr F composition(const F &f, const F &g) {}
  static constexpr F id() {}
};
*/
#line 4 "structure/segment-tree/lazy-segment-tree.hpp"

template <typename ActedMonoid>
struct LazySegmentTree {
  using S = typename ActedMonoid::S;
  using F = typename ActedMonoid::F;

 private:
  ActedMonoid m;

  int n{}, sz{}, height{};

  vector<S> data;

  vector<F> lazy;

  inline void update(int k) {
    data[k] = m.op(data[2 * k + 0], data[2 * k + 1]);
  }

  inline void all_apply(int k, const F& x) {
    data[k] = m.mapping(data[k], x);
    if (k < sz) lazy[k] = m.composition(lazy[k], x);
  }

  inline void propagate(int k) {
    if (lazy[k] != m.id()) {
      all_apply(2 * k + 0, lazy[k]);
      all_apply(2 * k + 1, lazy[k]);
      lazy[k] = m.id();
    }
  }

 public:
  LazySegmentTree() = default;

  explicit LazySegmentTree(ActedMonoid m, int n) : m(m), n(n) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    data.assign(2 * sz, m.e());
    lazy.assign(2 * sz, m.id());
  }

  explicit LazySegmentTree(ActedMonoid m, const vector<S>& v)
      : LazySegmentTree(m, static_cast<int>(v.size())) {
    build(v);
  }

  void build(const vector<S>& v) {
    assert(n == (int)v.size());
    for (int k = 0; k < n; k++) data[k + sz] = v[k];
    for (int k = sz - 1; k > 0; k--) update(k);
  }

  void set(int k, const S& x) {
    k += sz;
    for (int i = height; i > 0; i--) propagate(k >> i);
    data[k] = x;
    for (int i = 1; i <= height; i++) update(k >> i);
  }

  S get(int k) {
    k += sz;
    for (int i = height; i > 0; i--) propagate(k >> i);
    return data[k];
  }

  S operator[](int k) { return get(k); }

  S prod(int l, int r) {
    if (l >= r) return m.e();
    l += sz;
    r += sz;
    for (int i = height; i > 0; i--) {
      if (((l >> i) << i) != l) propagate(l >> i);
      if (((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    S L = m.e(), R = m.e();
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L = m.op(L, data[l++]);
      if (r & 1) R = m.op(data[--r], R);
    }
    return m.op(L, R);
  }

  S all_prod() const { return data[1]; }

  void apply(int k, const F& f) {
    k += sz;
    for (int i = height; i > 0; i--) propagate(k >> i);
    data[k] = m.mapping(data[k], f);
    for (int i = 1; i <= height; i++) update(k >> i);
  }

  void apply(int l, int r, const F& f) {
    if (l >= r) return;
    l += sz;
    r += sz;
    for (int i = height; i > 0; i--) {
      if (((l >> i) << i) != l) propagate(l >> i);
      if (((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= height; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template <typename C>
  optional<int> find_first(int l, const C& check) {
    if (l >= n) return nullopt;
    l += sz;
    for (int i = height; i > 0; i--) propagate(l >> i);
    S sum = m.e();
    do {
      while ((l & 1) == 0) l >>= 1;
      if (check(m.op(sum, data[l]))) {
        while (l < sz) {
          propagate(l);
          l <<= 1;
          auto nxt = m.op(sum, data[l]);
          if (not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = m.op(sum, data[l++]);
    } while ((l & -l) != l);
    return nullopt;
  }

  template <typename C>
  optional<int> find_last(int r, const C& check) {
    if (r <= 0) return nullopt;
    r += sz;
    for (int i = height; i > 0; i--) propagate((r - 1) >> i);
    S sum = m.e();
    do {
      r--;
      while (r > 1 and (r & 1)) r >>= 1;
      if (check(m.op(data[r], sum))) {
        while (r < sz) {
          propagate(r);
          r = (r << 1) + 1;
          auto nxt = m.op(data[r], sum);
          if (not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = m.op(data[r], sum);
    } while ((r & -r) != r);
    return nullopt;
  }
};
#line 5 "structure/heap/partially-retroactive-priority-queue.hpp"

template <typename T, typename Compare = std::less<T> >
struct PartiallyRetroactivePriorityQueue {
 private:
  enum class OperationType : uint8_t { NOOP, PUSH, POP };

  struct Operation {
    OperationType type = OperationType::NOOP;
    optional<T> value;
    bool alive = false;
  };

  struct CandidateNode {
    int alive_min = -1;
    int deleted_max = -1;
  };

  int n;
  int operation_count;
  int seg_size;
  Compare compare;

  vector<Operation> operations;
  vector<CandidateNode> candidates;
  // A deleted push has weight +1, a surviving push has weight 0, and a pop
  // has weight -1. Their prefix sums are nonnegative, and a zero is a bridge.
  // Updating one operation is a suffix addition on the prefix-sum array.
  LazySegmentTree<RangeAddRangeMin<int> > prefix;

  // A batch of n virtual values with lower priority than every real value is
  // inserted before the timeline. It makes every pop valid; popping one of
  // them is exactly an ignored pop on an empty real queue.
  int dummy_alive;
  int dummy_deleted = 0;

  int present_size = 0;
  T present_sum{};

  bool key_less(int a, int b) const {
    assert(a >= 0 and b >= 0);
    if (a == b) return false;
    if (a == 0) return false;
    if (b == 0) return true;
    const T& x = *operations[a - 1].value;
    const T& y = *operations[b - 1].value;
    if (compare(x, y)) return true;
    if (compare(y, x)) return false;
    return a < b;
  }

  int min_id(int a, int b) const {
    if (a == -1) return b;
    if (b == -1) return a;
    return key_less(a, b) ? a : b;
  }

  int max_id(int a, int b) const {
    if (a == -1) return b;
    if (b == -1) return a;
    return key_less(a, b) ? b : a;
  }

  void pull_candidate(int k) {
    candidates[k].alive_min =
        min_id(candidates[2 * k].alive_min, candidates[2 * k + 1].alive_min);
    candidates[k].deleted_max = max_id(candidates[2 * k].deleted_max,
                                       candidates[2 * k + 1].deleted_max);
  }

  void refresh_candidate(int p) {
    CandidateNode node;
    if (p == 0) {
      if (dummy_alive > 0) node.alive_min = 0;
      if (dummy_deleted > 0) node.deleted_max = 0;
    } else {
      const auto& op = operations[p - 1];
      if (op.type == OperationType::PUSH) {
        if (op.alive) {
          node.alive_min = p;
        } else {
          node.deleted_max = p;
        }
      }
    }
    int k = p + seg_size;
    candidates[k] = node;
    while (k >>= 1) pull_candidate(k);
  }

  int range_min_alive(int l, int r) const {
    int ret = -1;
    for (l += seg_size, r += seg_size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = min_id(ret, candidates[l++].alive_min);
      if (r & 1) ret = min_id(ret, candidates[--r].alive_min);
    }
    assert(ret != -1);
    return ret;
  }

  int range_max_deleted(int l, int r) const {
    int ret = -1;
    for (l += seg_size, r += seg_size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = max_id(ret, candidates[l++].deleted_max);
      if (r & 1) ret = max_id(ret, candidates[--r].deleted_max);
    }
    assert(ret != -1);
    return ret;
  }

  void add_weight(int p, int x) { prefix.apply(p + 1, operation_count + 1, x); }

  int find_first_zero(int l) {
    auto ret = prefix.find_first(l, [](int x) { return x == 0; });
    assert(ret.has_value());
    return *ret - 1;
  }

  int find_last_zero(int r) {
    auto ret = prefix.find_last(r + 1, [](int x) { return x == 0; });
    assert(ret.has_value());
    return *ret;
  }

  void promote(int id) {
    if (id == 0) {
      assert(dummy_deleted > 0);
      --dummy_deleted;
      ++dummy_alive;
      add_weight(0, -1);
      refresh_candidate(0);
      return;
    }
    auto& op = operations[id - 1];
    assert(op.type == OperationType::PUSH and not op.alive);
    op.alive = true;
    add_weight(id, -1);
    ++present_size;
    present_sum += *op.value;
    refresh_candidate(id);
  }

  void demote(int id) {
    if (id == 0) {
      assert(dummy_alive > 0);
      --dummy_alive;
      ++dummy_deleted;
      add_weight(0, 1);
      refresh_candidate(0);
      return;
    }
    auto& op = operations[id - 1];
    assert(op.type == OperationType::PUSH and op.alive);
    op.alive = false;
    add_weight(id, 1);
    --present_size;
    present_sum -= *op.value;
    refresh_candidate(id);
  }

  void check_time(int t) const { assert(0 <= t and t < n); }

  static int checked_size(int size) {
    assert(size >= 0);
    return size;
  }

 public:
  explicit PartiallyRetroactivePriorityQueue(int size,
                                             Compare comparator = Compare())
      : n(checked_size(size)),
        operation_count(n + 1),
        seg_size(1),
        compare(std::move(comparator)),
        operations(n),
        prefix(RangeAddRangeMin<int>(), vector<int>(n + 2)),
        dummy_alive(n) {
    while (seg_size < operation_count) seg_size <<= 1;
    candidates.assign(2 * seg_size, CandidateNode{});
    refresh_candidate(0);
  }

  /** Replaces operation t by push(value). */
  void set_push(int t, T value) {
    check_time(t);
    set_noop(t);
    int p = t + 1;
    auto& op = operations[t];
    op.type = OperationType::PUSH;
    op.value.emplace(std::move(value));
    op.alive = false;
    add_weight(p, 1);
    refresh_candidate(p);

    int bridge = find_last_zero(p);
    promote(range_max_deleted(bridge, operation_count));
  }

  /** Replaces operation t by pop. It is ignored when the queue is empty. */
  void set_pop(int t) {
    check_time(t);
    set_noop(t);
    int p = t + 1;

    int bridge = find_first_zero(p + 1);
    demote(range_min_alive(0, bridge));

    auto& op = operations[t];
    op.type = OperationType::POP;
    op.value.reset();
    op.alive = false;
    add_weight(p, -1);
  }

  /** Replaces operation t by a no-op. */
  void set_noop(int t) {
    check_time(t);
    int p = t + 1;
    auto& op = operations[t];
    if (op.type == OperationType::NOOP) return;

    if (op.type == OperationType::POP) {
      int bridge = find_last_zero(p);
      int id = range_max_deleted(bridge, operation_count);
      add_weight(p, 1);
      promote(id);
    } else if (op.alive) {
      --present_size;
      present_sum -= *op.value;
    } else {
      int bridge = find_first_zero(p + 1);
      int id = range_min_alive(0, bridge);
      demote(id);
      add_weight(p, -1);
    }

    op.type = OperationType::NOOP;
    op.alive = false;
    refresh_candidate(p);
    op.value.reset();
  }

  bool empty() const { return present_size == 0; }

  int size() const { return present_size; }

  const T& top() const {
    assert(not empty());
    int id = candidates[1].alive_min;
    assert(id > 0);
    return *operations[id - 1].value;
  }

  T sum() const { return present_sum; }
};

Back to top page