题解 | #数组中的逆序对#

const int maxn=1e5+5;
const int mod=1e9+7;
class Solution {
public:

    #define lowbit(x) x&(-x)

    int sum[100005];
    vector<int> p;
    void add( int x ) { while(x<maxn ){ sum[x]++,x+=lowbit(x);} };
    int query( int x ,int ans=0 ) {while(x)ans=(ans+sum[x])%mod,x-=lowbit(x);return ans; } 
    int getId( int x ) { return lower_bound(p.begin(),p.end(),x)-p.begin()+1; }
    int InversePairs(vector<int> data) {
        p.clear();
        for( int v:data ) p.push_back(1e5-v);
        sort(p.begin(),p.end());
        p.erase(unique(p.begin(),p.end()),p.end());

        int ans=0;
        for( int v:data ){
            v=1e5-v;
            v=getId(v);
            add(v);
            ans=(ans+query(v-1))%mod;
        }
        return ans;
    }
};