【luoguP2995】[USACO10NOV]牛的照片Cow Photographs

题目链接

首先求出原序列的逆序对个数，

然后考虑每次将目标序列最前面的数放在最后，即最小的数变为最大

设最小数的位置是\(p\)，那么逆序对的个数增加了\(n-p\)，减少了\(p-1\)

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;

const int MAXN=100010;

int n,a[MAXN],pos[MAXN],cnt,ans;

int tree[MAXN<<1];

inline int lowbit(int x){
    return x&(-x);
}

int query(int x){
    int ans=0;
    for(;x;x-=lowbit(x))
        ans+=tree[x];
    return ans;
}

inline void update(int x,int d){
    for(;x<=n;x+=lowbit(x))
        tree[x]+=d;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        cnt+=i-1-query(a[i]);
        update(a[i],1);
    }
    ans=cnt;
    for(int i=1;i<=n;++i){
        cnt+=n-pos[i]-pos[i]+1;
        ans=min(ans,cnt);
    }
    printf("%lld\n",ans);
    return 0;
}