求逆序对个数归并排序模板

#include<bits/stdc++.h>

using namespace std;

char seq[2000005];

int a[2000005];

int b[2000005];

int len;

long long int ans=0;

void Merge(int first,int middle,int last)

{

    int i,j,k;

    i=first;

    j=middle+1;

    k=0;

    while(i<=middle&&j<=last)

    {

        if(a[i]<=a[j])b[++k]=a[i++];

        else ans+=middle-i+1,b[++k]=a[j++];

    }

    while(i<=middle)b[++k]=a[i++];

    while(j<=last)b[++k]=a[j++];

    for(i=1;i<=k;i++)a[first+i-1]=b[i];

}

void MergeSort(int Start,int End)

{

    if(Start<End)

    {

        int Mid=(Start+End)/2;

        MergeSort(Start,Mid);

        MergeSort(Mid+1,End);

        Merge(Start,Mid,End);

    }

}

int main()

{

    scanf("%s",seq+1);

    len=strlen(seq+1);

    for(int i=1;i<=len;i++)a[i]=seq[i]-'A'+1;

    MergeSort(1,len);

    printf("%lld",ans);

    return 0;

}