模板_求排列逆序对_基于归并排序

//
#include<bits/stdc++.h>
using namespace std;
#define int long long               // 大数据量

const int N=1e5+6;
int in[N];
int ans;

void merge( int x1,int y1,int x2,int y2 )
{
    int tt[N];
    int i=x1,j=x2,pos=0;
    while( i<=y1 && j<=y2 )         // j-( x1+pos ) 位置差
    {
        if( in[i]<=in[j] )  tt[pos++]=in[i++];
        else    { ans+=j-( x1+pos ); tt[pos++]=in[j++]; }
    }
    while( i<=y1 ) tt[pos++]=in[i++];
    while( j<=y2 ) tt[pos++]=in[j++];
    for( i=0;i<pos;i++ ) in[x1+i]=tt[i];
}

void f( int x,int y )
{
    if( x==y ) return ;
    int mid=( x+y )>>1;
    f( x,mid );
    f( mid+1,y );
    merge( x,mid,mid+1,y );
}

signed main()
{
    int n,i;
    
    while( cin>>n )
    {
        for( i=0;i<n;i++ ) cin>>in[i];
        ans=0;
        f( 0,n-1 );
        cout<<ans<<endl;
    }
    return 0;
}