structure/bipq.hpp

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

Depends on

• structure/erasablepq.hpp

Code

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

template <class T>
struct bipq {
    erasablepq<T> q;
    erasablepqg<T> qg;
    void push(const T& x) { q.push(x); qg.push(x); }
    void erase(const T& x) { q.erase(x); qg.erase(x); }
    void pop_max() {
        qg.erase(q.top());
        q.pop();
    }
    void pop_min() {
        q.erase(qg.top());
        qg.pop();
    }
    T top_max() { return q.top(); }
    T top_min() { return qg.top(); }
    int size() { return q.size(); }
    bool empty() { return q.empty(); }
};

#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();
        }
    }
};
#line 4 "structure/bipq.hpp"
using namespace std;

template <class T>
struct bipq {
    erasablepq<T> q;
    erasablepqg<T> qg;
    void push(const T& x) { q.push(x); qg.push(x); }
    void erase(const T& x) { q.erase(x); qg.erase(x); }
    void pop_max() {
        qg.erase(q.top());
        q.pop();
    }
    void pop_min() {
        q.erase(qg.top());
        qg.pop();
    }
    T top_max() { return q.top(); }
    T top_min() { return qg.top(); }
    int size() { return q.size(); }
    bool empty() { return q.empty(); }
};

Back to top page