最开始有一个长度为 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` 函数用于查询平衡树中某个节点的排名。在主函数中，我们使用平衡树来维护序列，并在加入新元素时输出其排名。