structure/erasablepq.hpp

• View this file on GitHub
• Last update: 2025-11-18 00:25:38+09:00
• Include: #include "structure/erasablepq.hpp"

Required by

• structure/bipq.hpp

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;

template <class T>
struct erasablepq {
    priority_queue<T> pq, del;
    void push(const T& x) {
        pq.push(x);
        normalize();
    }
    void erase(const T& x) {
        del.push(x);
        normalize();
    }
    void pop() {
        pq.pop();
        normalize();
    }
    T top() {
        return pq.top();
        normalize();
    }
    bool empty() {
        return pq.empty();
        normalize();
    }
    int size() {
        return pq.size() - del.size();
    }
    void normalize() {
        while (!del.empty() && !pq.empty() && pq.top() == del.top()) {
            pq.pop();
            del.pop();
        }
    }
};

template <class T>
struct erasablepqg {
    priority_queue<T, vector<T>, greater<T>> pq, del;
    void push(const T& x) {
        pq.push(x);
        normalize();
    }
    void erase(const T& x) {
        del.push(x);
        normalize();
    }
    void pop() {
        pq.pop();
        normalize();
    }
    T top() {
        return pq.top();
        normalize();
    }
    bool empty() {
        return pq.empty();
        normalize();
    }
    int size() {
        return pq.size() - del.size();
    }
    void normalize() {
        while (!del.empty() && !pq.empty() && pq.top() == del.top()) {
            pq.pop();
            del.pop();
        }
    }
};

#line 2 "structure/erasablepq.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class T>
struct erasablepq {
    priority_queue<T> pq, del;
    void push(const T& x) {
        pq.push(x);
        normalize();
    }
    void erase(const T& x) {
        del.push(x);
        normalize();
    }
    void pop() {
        pq.pop();
        normalize();
    }
    T top() {
        return pq.top();
        normalize();
    }
    bool empty() {
        return pq.empty();
        normalize();
    }
    int size() {
        return pq.size() - del.size();
    }
    void normalize() {
        while (!del.empty() && !pq.empty() && pq.top() == del.top()) {
            pq.pop();
            del.pop();
        }
    }
};

template <class T>
struct erasablepqg {
    priority_queue<T, vector<T>, greater<T>> pq, del;
    void push(const T& x) {
        pq.push(x);
        normalize();
    }
    void erase(const T& x) {
        del.push(x);
        normalize();
    }
    void pop() {
        pq.pop();
        normalize();
    }
    T top() {
        return pq.top();
        normalize();
    }
    bool empty() {
        return pq.empty();
        normalize();
    }
    int size() {
        return pq.size() - del.size();
    }
    void normalize() {
        while (!del.empty() && !pq.empty() && pq.top() == del.top()) {
            pq.pop();
            del.pop();
        }
    }
};

Back to top page