题解 | #Inverse Pair#

题目描述：
给你一个数组a，a[i]可以加1或者不加，求进行所有操作完后最小的逆序对数
思路：
先把所有的逆序对数求出来，然后再找满足(a[i]>a[j]&&i<j&&a[i]==a[j]+1)条件的对数，再用所有的逆序对数减去满足条件对数就可以的出最小对数。
AC代码

#include<bits/stdc++.h>
using namespace std;
int num[200005];
int b[200005],ans[200005];
long long sum=0;
void gbsort(int l,int r,int a[])
{
    int mid=(l+r)/2;
    if(l==r) return;
    else
    {
        gbsort(l,mid,a);
        gbsort(mid+1,r,a);
    }
    int i=l,t=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            sum+=mid+1-i;
            b[t++]=a[j++];
        }
        else
        {
            b[t++]=a[i++];
        }
    }
    while(i<=mid)
        b[t++]=a[i++];
    while(j<=r)
        b[t++]=a[j++];
    for(int i=l;i<=r;i++ )
    {
        a[i]=b[i];
    }
    return;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>ans[i];
        num[ans[i]]=i;
    }
    gbsort(0,n-1,ans);
    for(int i=1;i<n;i++){
        if(num[i]>num[i+1]){
            sum--;
            i++;
        }
    }
    cout<<sum<<'\n';
    return 0;
}