别的方法我不知道,我知道这题用multiset很简单.

multiset(以及set)可以执行插入,二分查找,删除等操作,与set的区别在于它不会自动去重.multiset在任意时刻可以保持内部元素的有序性.

并且提到的这三种操作的复杂度都是O(logN).

一种常见的做法(不限于此题)是插入两个"哨兵"初始化multiset(及set),使得查找操作无论如何都不会返回不存在的迭代器位置.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;

multiset<int> s;

int main(){
    int q;
    scanf("%d", &q);
    s.insert(2147483647);
    s.insert(-2147483647);

    while(q--){
        int x, opr;
        scanf("%d%d", &opr, &x);

        if(opr == 1){
            int ans = 0;
            auto pos = s.lower_bound(x);
            for(auto i = s.begin(); i != pos; i++) ans++;
            printf("%d\n", ans);
        }else if(opr == 2){
            auto pos = s.begin();
            while(x--) pos++;
            // pos--;
            printf("%d\n", *pos);
        }else if(opr == 3){
            auto pos = s.lower_bound(x);
            pos--;
            printf("%d\n", *pos);
        }else if(opr == 4){
             printf("%d\n", *s.upper_bound(x));
        }else
            s.insert(x);
    }

    return 0;
}

P5076