牛4 I:Inverse Pair

题面：已知有1到n的排列，每个数可以加1或是加0，求逆序数最小是多少。
解析：一个排序的逆序数已经是固定的，逆序数减少就说明一个数字x的后面出现了x-1,x不变，x-1再加1。记录逆序数减少的个数，可以从后往前推，用h[]存数字是否出现,加以判断即可。
求逆序数用树状数组。
代码：

#include<stdio.h>
#include<algorithm> 
#define MAXN 5000001
using namespace std;
typedef long long ll;
ll bt[MAXN]={0},n,h[MAXN],ans;
ll a[MAXN];
void add(ll x,ll k){
    while(x<=n){
        bt[x]+=k;
        x+=x&(-x);
    }
}
ll sum(ll x){
    ll ans=0;
    while(x){
        ans+=bt[x];
        x-=x&(-x);
    }
    return ans;
}
int ha[MAXN]={0};
int t;
ll cn=0;
int main(){
//    scanf("%d",&t);
//    while(t--){

    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
    scanf("%lld",&a[i] );
    }
    for(ll i=1;i<=n;i++){
    add(a[i],1);
    ans+=i-sum(a[i]);    
    }//求逆序数

     ha[n+1]=1;//使n不能加1
    for(int i=n;i>0;i--)
     if(ha[a[i]]==0&&ha[a[i]+1]==0)//如果a[i]和a[i+1]都没出现过
{cn++;ha[a[i]]=1;ha[a[i]+1]=1;}
    else if(ha[a[i]]==0&&ha[a[i]+1]==1) ha[a[i]]=1;//标记a[i]
    printf("%lld\n",ans-cn);

//}
}