题解 | 第 k 小

求第k小，可以使用邪教的pbds操作，具体调用方法详见代码。

#include "bits/stdc++.h"

/*
________  _______       ___         ___      ________      ________
|\  _____\|\  ___ \     |\  \       |\  \    |\   __  \    |\   __  \
\ \  \__/ \ \   __/|    \ \  \      \ \  \   \ \  \|\  \   \ \  \|\  \
 \ \   __\ \ \  \_|/__   \ \  \   __ \ \  \   \ \  \\\  \   \ \   __  \
  \ \  \_|  \ \  \_|\ \   \ \  \ |\  \\_\  \   \ \  \\\  \   \ \  \ \  \
   \ \__\    \ \_______\   \ \__\\ \________\   \ \_______\   \ \__\ \__\
    \|__|     \|_______|    \|__| \|________|    \|_______|    \|__|\|__|
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define endl "\n"
#define PII pair<int,int>


template<typename T>
using ordered_set = tree<
    T,
    null_type,
    less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;
//ordered_multiset<pair<int, int>> == multiset;
class PBDSMultiSet {
private:
    using pii = pair<int, int>;
    using Tree = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;

    Tree ms;
    int uid = 0;  // 用于区分重复元素

public:
    void insert(int x) {
        ms.insert({x, uid++});
    }

    void erase(int x) {
        auto it = ms.lower_bound({x, 0});
        if (it != ms.end() && it->first == x) {
            ms.erase(it);
        }
    }

    int count(int x) {
        return ms.order_of_key({x + 1, 0}) - ms.order_of_key({x, 0});
    }

    int size() const {
        return ms.size();
    }

    int kth(int k) {  // k 从 0 开始
        if (k < 0 || k >= (int)ms.size()) return -1;
        return ms.find_by_order(k)->first;
    }

    int rank(int x) {  // 小于 x 的数量
        return ms.order_of_key({x, 0});
    }

    bool empty() const {
        return ms.empty();
    }

    void clear() {
        ms.clear();
        uid = 0;
    }
};

//map
template<typename Key, typename Value>
class PBDSMap {
private:
    using omap = tree<
        Key, Value, less<Key>,
        rb_tree_tag,
        tree_order_statistics_node_update
    >;

    omap mp;

public:
    Value& operator[](const Key& k) {
        return mp[k];  // 自动插入默认值
    }

    bool contains(const Key& k) const {
        return mp.find(k) != mp.end();
    }

    void erase(const Key& k) {
        mp.erase(k);
    }

    int size() const {
        return mp.size();
    }

    int rank(const Key& k) const {
        return mp.order_of_key(k);
    }

    pair<Key, Value> kth(int k) const {
        if (k < 0 || k >= (int)mp.size()) throw out_of_range("k out of range");
        auto it = mp.find_by_order(k);
        return {it->first, it->second};
    }

    void clear() {
        mp.clear();
    }
};

/*
https://codeforces.com/problemset/problem/1915/F
| 功能       | 接口                  | 复杂度           |
| -------- | ------------------- | ------------- |
| 插入元素     | `insert(x)`         | log n |
| 删除元素     | `erase(x)`-'erase(lower_bound(x))'          | log n |
| 第 k 小     | `*find_by_order(k)` | log n |
| 小于 x 的数量 | `order_of_key(x)`   | log n |
| 支持重复元素   | 插入 `pair<val, id>`  | log n |
| 查询元素排名   | `order_of_key(x)`   | log n |

*/





/*

*/

void slu() {
    int n , m , k;
    PBDSMultiSet s;
    cin >> n >> m >> k;
    for (int i = 0 ; i < n ; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    for(int i = 0 ; i < m ; i++){
        int coi ;
        cin >> coi;
        if (coi == 1) {
            int x;
            cin >> x;
            s.insert(x);
        }
        else cout << s.kth(k - 1) << endl;
    }

}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}