逆序对模板（归并排序/树状数组）

class Solution {
public:
    typedef long long LL;
    // // 1
    // // Merge_Sort
    // LL ans;
    // template<class Array> void count(int left,int right,Array& A,Array& B){
    //     if(left>=right) return;
    //     // cout<<"("<<left<<","<<right<<")"<<endl;
    //     int mid=right+left>>1;//优先级的坑+1: p(+)>p(>>)
    //     count(left,mid,A,B); count(mid+1,right,A,B);
    //     int i=left,j=mid+1,k=left;
    //     while(i<=mid || j<=right){
    //         if(j>right || (i<=mid && A[i]<=A[j]))
    //             B[k++]=A[i++];
    //         else B[k++]=A[j++],ans+= mid-i+1;
    //     }
    //     for(int i=left;i<=right;i++) A[i]=B[i];
    // }
    // inline void init(){ans=0;}
    // int reversePairs(vector<int>& nums) {
    //     init();
    //     vector<int> empty; empty.resize(nums.size());
    //     count(0,nums.size()-1,nums,empty);
    //     return ans;
    // }

    // // 2
    // Binary Indexed Tree(B.I.T)
    // 逆序对定义 Σ[i](1,n,Σ[j](1,i-1,A[j]>A[i]))
    // 前（后）面有几个比我大（小）之和
    // 不断地插入，查询 `我的位置-【 前面有几个比我“小”之和】`
    struct node{
        int idx,val;
        node(){};
        node(int idx,int val):idx(idx),val(val){}
        bool operator<(node b){
            // 忘了考虑val相等地情况 还有 sort的随机性
            // 突然想念merge_sort的好
            if(val!=b.val)
                return val<b.val;
            return idx<b.idx;
        }
    };
    inline int lowbit(int x){return x&(-x);}
    template<class Array>
    inline void update(int x,int n,Array& A){
        while(x<=n){
#ifdef DEBUG
            cout<<"+"<<x-1<<endl;
#endif
            A[x-1]+=1;
            x+=lowbit(x);
        }
    }
    template<class Array>
    inline int query(int x,Array& A){
        int res=0;
        while(x){
#ifdef DEBUG
            cout<<"="<<x-1<<endl;
#endif
            res+=A[x-1];
            x-=lowbit(x);
        }
        return res;
    }
    int reversePairs(vector<int>& nums) {
        LL ans=0;
        vector<node> sorted_nums;
        vector<int> discrete,tree;

        discrete.resize(nums.size());
        tree.resize(nums.size());

        for(int i=0;i<nums.size();i++)
            sorted_nums.push_back(node(i,nums[i]));
        sort(sorted_nums.begin(),sorted_nums.end());
#ifdef DEBUG
        for(auto x: sorted_nums) cout<<x.idx<<" "<<x.val<<endl;
#endif
        // 离散化
        for(int i=0;i<sorted_nums.size();i++)
            discrete[sorted_nums[i].idx]=i+1;
        
        for(int i=0;i<discrete.size();i++){
            update(discrete[i],tree.size(),tree);
            ans+=i+1-query(discrete[i],tree);
        }
        return ans;
    }
};

---

本文章使用limfx的vsocde插件快速发布