思路

set

set 是一个 STL 里的关联式容器，其内部是平衡树（红黑树），维护一个有序集合。

下面介绍两种本题需要用到的 set 支持的操作。

1. s.insert(x) 在集合 $s$ 中插入一个元素 $x$。
2. s.lower_bound(x) 在集合 $s$ 中查找第一个大于等于 $x$ 的元素的地址。

需要注意的几点

• 遍历 set 用的是地址变量，要在前面加指针符号才能得到数值。

• set 自带去重，但本题中是不要去重的，这里要用多重集合 multiset。

实现

• $op=1$

  直接插入即可。

  a.insert(x);
  

• $op=2$

  先找到第一个小于等于 $x$ 的位置，然后往后跳 $k$ 位置，一边跳一边判断是否越界。

  cin >> k;
  auto ans = a.upper_bound(x);
      //auto 表示自动识别变量类型
  
  while (ans != a.begin() && k)
     k--, ans--;
  
  if (k)
      cout << "-1\n";
      //如果此时 k 仍然大于 0 ，说明不存在第 k 大的元素
  
  else
      cout << *ans << '\n';
  

• $op=3$

  同理。

  不过，要注意的是，lower_bound(x) 这个位置是所有大于等于 $x$ 的元素中的最大值， $ans$ 的初始地址已经包括了一个元素，因此 $k$ 要少往后跳一次。

  cin >> k;
  auto ans = a.lower_bound(x);
  
  while (ans != a.end() && k > 1)
      k--, ans++;
  
  if (ans == a.end())
      cout << "-1\n";
      //如果 ans 已经跳到末尾，说明没有第 k 小的元素
  
  else
      cout << *ans << '\n';
  

复杂度证明

由于 set 内部是红黑树，其所有操作复杂度均为 $O(\operatorname{log}n)$ 。

然后每次查询最多往前后查 $k$ 个元素，而 $k≤5$ 。

代码

#include <bits/stdc++.h>
using namespace std;

long long q , x, k, op;
multiset<long long> a;

int main() {
	cin >> q;
	
    while (q--) {
        op, x;
        cin >> op >> x; 
        if (op == 1)
            a.insert(x);
        else if (op == 2) {
            cin >> k;
            auto ans = a.upper_bound(x);

            while (ans != a.begin() && k)
                k--, ans--;

            if (k)
                cout << "-1\n";
            else
                cout << *ans << '\n';
        } else {
            cin >> k;
            auto ans = a.lower_bound(x);

            while (ans != a.end() && k > 1)
                k--, ans++;

            if (ans == a.end())
                cout << "-1\n";
            else
                cout << *ans << '\n';
        }
    }

    return 0;
}