题解 | 数组中的逆序对

#include <algorithm>
#include <vector>
class AntiOrder {
  public:
    int count(vector<int> A, int n) {
        // write code here
        const int mod = 1e9 + 7;
        vector<int> sortedA = A;
        sort(sortedA.begin(), sortedA.end());
        sortedA.erase(unique(sortedA.begin(), sortedA.end()), sortedA.end());
        auto getRank = [&](int x) {
            return lower_bound(sortedA.begin(), sortedA.end(), x) - sortedA.begin() + 1;
        };
        vector<int> BIT(sortedA.size() +2);
        auto update = [&](int x){
            while (x < BIT.size() ) {
                BIT[x] +=1;
                x += x& (-x);        
            }

        };
        auto query = [&](int x) {
            int res =0;
            while (x>0) {
                res += BIT[x];
                x -= x& (-x);
            
            }
            return res;
        };
        int res = 0;
        for(int i=n-1; i>=0;--i){
            int rank = getRank(A[i]);
            res = (res + query(rank -1)) %mod;
            update(rank);

        }
        return res;


    }
};