最开始有一个长度为 0 0 的序列，需要对序列进行 � n 次操作。 每个操作用 � p 和 � x 两个参数表示： 如果 � = 0 p=0，表示向序列中加入 � x； 如果 � = 1 p=1，表示询问序列从大到小第 � x 大的数；没有其他的情况。 因为某种特殊性质，每次插入的数一定是从大到小排序后在前 � m 的数。c++代码

以下是使用 STL 中的 multiset 实现的 C++ 代码：

#include <iostream>
#include <set>
using namespace std;

multiset<int, greater<int>> s;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int op, p, x;
        cin >> op >> p >> x;
        if (op == 0) {
            s.insert(x);
        } else {
            auto it = s.begin();
            advance(it, x - 1);
            cout << *it << endl;
        }
    }
    return 0;
}

其中，`multiset<int, greater<int>> s` 定义了一个降序的 multiset，`s.begin()` 返回的是指向最大值的迭代器，`advance(it, x - 1)` 将迭代器移动到第 `x` 大的位置上，`*it` 即为第 `x` 大的数。

相关问题

最开始有一个长度为 0 0 的序列，需要对序列进行 � n 次操作。每个操作用 p 和 x 两个参数表示： 如果 = 0 p=0，表示向序列中加入 x; 如果 = 1 p=1，表示询问序列从大到小第 x 大的数;没有其他的情况。因为某种特殊性质，每次插入的数一定是从大到小排序后在前 � m 的数。用c++写

以下是使用堆实现的 C++ 代码：

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> q;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int op, p, x;
        cin >> op >> p >> x;
        if (op == 0) {
            if (q.size() < p) { // 只保留前 m 大的数
                q.push(x);
            } else if (x > q.top()) { // 如果 x 比当前最小值大，则删除最小值，并插入 x
                q.pop();
                q.push(x);
            }
        } else {
            cout << q.top() << endl;
        }
    }
    return 0;
}

其中，`priority_queue<int, vector<int>, greater<int>> q` 定义了一个小根堆，`q.top()` 返回堆顶元素，即最小值。在插入元素时，如果堆的大小小于 `m`，则直接插入；如果堆的大小已经为 `m`，则比较插入的元素和堆顶元素的大小，若插入的元素更大，则删除堆顶元素，并插入该元素。

最开始有一个长度为 0 0 的序列，需要对序列进行 � n 次操作。每次操作会给出一个整数 � x，你需要将它加入序列并且输出这个数是从大到小排名第几个数。 因为某种特殊性质，除第一个数以外，新加的数一定和现有的数都不一样，并且与上一个数相比差不会超过 [ − � . . � ] [−m..m]。例如 � = 10 m=10，上一个数是 20 20，那么新加的数在 [ 10..30 ] [10..30] 范围内。c++代码

以下是一种使用平衡树（如红黑树）实现的方法，时间复杂度为 $O(n \log n)$：

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

template<typename T>
struct Tree {
    struct Node {
        T val;
        int size, cnt;
        Node *ls, *rs;

        Node(T val) : val(val), size(1), cnt(1), ls(nullptr), rs(nullptr) {}
        ~Node() { delete ls; delete rs; }
    } *root;

    Tree() : root(nullptr) {}
    ~Tree() { delete root; }

    int size(Node *p) { return p ? p->size : 0; }

    void update(Node *p) {
        p->size = size(p->ls) + p->cnt + size(p->rs);
    }

    void left_rotate(Node *&p) {
        Node *q = p->rs;
        p->rs = q->ls;
        q->ls = p;
        update(p); update(q);
        p = q;
    }

    void right_rotate(Node *&p) {
        Node *q = p->ls;
        p->ls = q->rs;
        q->rs = p;
        update(p); update(q);
        p = q;
    }

    void maintain(Node *&p) {
        if (size(p->ls) > size(p->rs) * 2) {
            if (size(p->ls->rs) > size(p->ls->ls))
                left_rotate(p->ls);
            right_rotate(p);
        } else if (size(p->rs) > size(p->ls) * 2) {
            if (size(p->rs->ls) > size(p->rs->rs))
                right_rotate(p->rs);
            left_rotate(p);
        }
    }

    void insert(Node *&p, T val) {
        if (!p) p = new Node(val);
        else if (val < p->val) insert(p->ls, val);
        else if (val > p->val) insert(p->rs, val);
        else p->cnt++;
        update(p);
        maintain(p);
    }

    int get_rank(Node *p, T val) {
        if (!p) return 1;
        else if (val < p->val) return get_rank(p->ls, val);
        else if (val > p->val) return get_rank(p->rs, val) + p->cnt + size(p->ls);
        else return size(p->ls) + 1;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;

    Tree<int> tr;

    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        int rank = tr.get_rank(tr.root, x);
        tr.insert(tr.root, x);
        cout << rank << '\n';
    }

    return 0;
}

其中 `Tree` 是平衡树的模板类，`Node` 是平衡树节点的结构体，包含节点的值、子树大小、出现次数以及左右儿子指针。`size` 函数返回节点的子树大小，`update` 函数用于更新节点的子树大小。 `left_rotate` 和 `right_rotate` 函数分别对平衡树进行左旋和右旋操作。`maintain` 函数用于维护平衡树的平衡性，使平衡树左右子树的大小之差不超过 $1$。`insert` 函数用于向平衡树中插入新节点，`get_rank` 函数用于查询平衡树中某个节点的排名。在主函数中，我们使用平衡树来维护序列，并在加入新元素时输出其排名。