Removable Priority Queue
(data_structure/removable_priority_queue.hpp)

• View this file on GitHub
• Last update: 2024-03-08 13:39:50+09:00
• Include: #include "data_structure/removable_priority_queue.hpp"
• Link: https://atcoder.jp/contests/abc218/submissions/25800862
• Link: https://twitter.com/maspy_stars/status/1436690222465486848

説明

constructor

removable_priority_queue() = default // (1)

removable_priority_queue(InputIterator first, InputIterator last) // (2)

• (1) デフォルトコンストラクタ
• (2) $[first, last)$ の要素で構築する $O(N)$

empty()

空であるかを判定する。 $O(1)$

size()

要素数を所得する。 $O(1)$

top()

優先度最大の要素を所得。 ならし $O(\log{N})$

pop()

優先度最大の要素を取り除く。 ならし $O(\log{N})$

push(T x)

x を追加。 $O(\log{N})$

emplace(Args &&…args)

要素型 T のコンストラクタ引数をとり、直接構築で要素を追加する。 $O(\log{N})$

remove(T x)

x を取り除く。 $O(\log {N})$

emplace_remove(Args &&…args)

要素型 T のコンストラクタ引数をとり、直接構築で要素を削除する。 $O(\log{N})$

Required by

• Double-Ended Priority Queue (data_structure/double_ended_priority_queue.hpp)

Verified with

• test/data_structure/Double-Ended_Priority_Queue.test.cpp

Code

#pragma once

#include <functional>
#include <queue>
#include <vector>

/*
    reference: https://twitter.com/maspy_stars/status/1436690222465486848
    verify: https://atcoder.jp/contests/abc218/submissions/25800862
*/

namespace ebi {

template <class T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
struct removable_priority_queue {
  private:
    void update() {
        while (!rm_que.empty() && que.top() == rm_que.top()) {
            que.pop();
            rm_que.pop();
        }
        return;
    }

  public:
    removable_priority_queue() = default;

    template <class InputIterator>
    removable_priority_queue(InputIterator first, InputIterator last) {
        que = std::priority_queue<T, Container, Compare>(first, last);
    }

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

    int size() const {
        return int(que.size() - rm_que.size());
    }

    T top() {
        assert(!empty());
        update();
        return que.top();
    }

    void pop() {
        assert(!empty());
        update();
        que.pop();
        return;
    }

    void push(const T &x) {
        que.push(x);
        return;
    }

    template <class... Args> void emplace(Args &&...args) {
        que.emplace(std::forward<Args>(args)...);
        return;
    }

    void remove(const T &x) {
        rm_que.push(x);
        assert(que.size() >= rm_que.size());
        return;
    }

    template <class... Args> void emplace_remove(Args &&...args) {
        rm_que.emplace(std::forward<Args>(args)...);
        assert(que.size() >= rm_que.size());
        return;
    }

  private:
    std::priority_queue<T, Container, Compare> que, rm_que;
};

}  // namespace ebi

#line 2 "data_structure/removable_priority_queue.hpp"

#include <functional>
#include <queue>
#include <vector>

/*
    reference: https://twitter.com/maspy_stars/status/1436690222465486848
    verify: https://atcoder.jp/contests/abc218/submissions/25800862
*/

namespace ebi {

template <class T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
struct removable_priority_queue {
  private:
    void update() {
        while (!rm_que.empty() && que.top() == rm_que.top()) {
            que.pop();
            rm_que.pop();
        }
        return;
    }

  public:
    removable_priority_queue() = default;

    template <class InputIterator>
    removable_priority_queue(InputIterator first, InputIterator last) {
        que = std::priority_queue<T, Container, Compare>(first, last);
    }

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

    int size() const {
        return int(que.size() - rm_que.size());
    }

    T top() {
        assert(!empty());
        update();
        return que.top();
    }

    void pop() {
        assert(!empty());
        update();
        que.pop();
        return;
    }

    void push(const T &x) {
        que.push(x);
        return;
    }

    template <class... Args> void emplace(Args &&...args) {
        que.emplace(std::forward<Args>(args)...);
        return;
    }

    void remove(const T &x) {
        rm_que.push(x);
        assert(que.size() >= rm_que.size());
        return;
    }

    template <class... Args> void emplace_remove(Args &&...args) {
        rm_que.emplace(std::forward<Args>(args)...);
        assert(que.size() >= rm_que.size());
        return;
    }

  private:
    std::priority_queue<T, Container, Compare> que, rm_que;
};

}  // namespace ebi

Back to top page