multiset + vector

用multiset存放集合，vector存放第k个插入元素的迭代器

C++ 代码

#include <multiset>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    multiset<int> st;
    vector<multiset<int>::iterator> vc;  // 存储第k个插入的数的迭代器
    int n;
    cin >> n;
    while(n --)
    {
        string op;
        cin >> op;
        if(op == "I")  // 插入元素O(log n)
        {
            int a;
            cin >> a;
            vc.push_back(st.insert(a));  // insert返回a元素插入的位置(multiset<int>::iterator)
        }
        else if(op == 'PM')  // 输出最小值O(1)
        {
            cout << *st.begin() << endl;
        }
        else if(op == "DM")  // 删除最小值O(log n)
        {
            st.erase(st.begin());
        }
        else if(op == "D")  //删除指定元素O(log n)
        {
            int k;
            cin >> k;
            st.erase(vc[k - 1]);
        }
        else if(op == "C")  //更改指定元素O(log n)
        {
            int k, c;
            cin >> k >> c;
            st.erase(vc[k - 1]);
            vc[k - 1] = st.insert(c);
        }
    }
    return 0;
}