消せるウンタラカンタラ

[Astral-23]

template<class pque, class S>struct deletable_priority_queue {
    pque P;
    pque Q;

    void balance() {
        while(P.empty() == false && Q.empty() == false && P.top() == Q.top()) {
            P.pop();Q.pop();
        }
    }

    void push(S x) {
        P.push(x);
    }

    void pop() {
        balance();
        P.pop();
    }

    void del(S x) {
        if(P.top() == x) pop();
        else Q.push(x);
    }

    S top() {
        balance();
        return P.top();
    }

    ll size() {
        return P.size() - Q.size();
    }

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

};