题目描述

blablabla

样例

blablabla

算法1

(分治) $O(n log n)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#define _for(i,a,b) for( int i=(a); i<(b); ++i)
#define _rep(i,a,b) for( int i=(a); i<=(b); ++i)
typedef long long ll;
using namespace std;
int n;
int arr[100010];
int tmp[100010];
long long ms(int q[],int l,int r){
    if(l>=r)
    return 0;
    int mid = l+r >> 1;
    long long leftAns = ms(q,l,mid);
    long long rightAns = ms(q,mid+1,r);
    int i = l,j = mid +1,midAns=0;
    while(j <= r){
        while(i<= mid && q[i] <= q[j])i++;
        midAns += mid+1-i;
        j++;
    }
    sort(q+l,q+r+1);
    return leftAns + rightAns + midAns;
}
int main() {

    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",arr+i);
    printf("%lld",ms(arr,0,n-1));
    // for(int i=0;i<n;i++)printf("%d ",arr[i]);

    return 0;
}