ABC241D 题解

FurippuWRY · 2023-09-23 12:33:09 · 题解

用 multiset 以及 upper_bound() 和 lower_bound() 做此题。

定义一个 multiset，命名为 a;

• 操作 1：用 a.insert(x) 插入元素 x；

• 操作 2：用 upper_bound() 查找，然后向前 k 个数，同时判断 k 是否等于 a.begin()，若等于，退出循环并且输出 -1，否则输出 a 中所有小于等于 x 的元素中的第 k 大值。

• 操作 3：与操作 2 类似，用 lower_bound() 查找，然后向后 k 个数，同时判断 k 是否等于 a.end()，若等于，退出循环并且输出 -1，否则输出 a 中所有大于等于 x 的元素中的第 k 小值。

#include <bits/stdc++.h>
#define int long long

using namespace std;

multiset<int> a;

int q, p, x, k;

signed main() {
    cin >> q;
    while (q--) {
        cin >> p >> x;
        if (p == 1) a.insert(x);
        if (p == 2) {
            cin >> k;
            multiset<int>::iterator n = a.upper_bound(x);
            while (n != a.begin() && k) {
                k--;
                n--;
            }
            if (k) cout << -1 << '\n';
            else cout << *n << '\n';
        }
        if (p == 3) {
            cin >> k;
            multiset<int>::iterator n = a.lower_bound(x);
            while (n != a.end() && k > 1) {
                k--;
                ++n;
            }
            if (n == a.end()) cout << -1 << '\n';
            else cout << *n << '\n';
        }
    }
    return 0;
}