逆序数（归并排序+树状数组）

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2， 那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

第一行有一个整数n(1 <= n <= 100000),  然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。

输出这个序列中的逆序数

示例1

复制

5
4 5 1 3 2

复制

7

const int MXA=1000010;
vectora;
//利用归并排序中b c二个数组都是排序好的性质
//如果bi&a){
    ll n;
    n=a.size();
    if(n<=1){
        return 0;
    }
    ll ans=0;
    vectorb(a.begin(),a.begin()+n/2);
    vectorc(a.begin()+n/2,a.end());
    ans+=merge_sort(b);
    ans+=merge_sort(c);
    int a1=0;
    int b1=0;
    int c1=0;
    while (a1>n;
    for(int i=0;i>x;
        a.push_back(x);
    }
    cout< 
const int MAX=10000010;
int a[MAX];
int bit[MAX];
int n;
int lowbit(int x){
    return  x&(-x);
}
void  add(int x,int val){
    while (x<=n) {
        bit[x]+=val;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while (x>0) {
        ans+=bit[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=0;i>a[i];
    }
    int ans=0;
    for(int i=0;i