题解 | 维护x的秩

#include <algorithm>
#include <vector>
class Rank {
  public:
    vector<int> getRankOfNumber(vector<int> A, int n) {
        // write code here
        vector<int> sorted(A);
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        auto get_id = [&](int x) {
            return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;

        };
        vector<int> BIT(n + 2, 0);
        auto update = [&](int x) {
            while (x < BIT.size()) {
                BIT[x]++;
                x += x & -x;
            }

        };
        auto query = [&](int x) {
            int res = 0;
            while (x > 0) {
                res += BIT[x];
                x -= x & -x;
            }
            return res;
        };
        vector<int> res(n,0);
        for (int i = 0; i < n; ++i) {
            int id = get_id(A[i]);
            res[i] = query(id - 1);
            update(id);
        }
        return res;

    }
};