P11208 『STA - R8』轮回疯狂

只 WA 一个点,#18: read - ,expected 9 我的提交

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
 
int n,a[N],contri[N],c[N],cnt;
//n个数 a是输入的排列 c是树状数组
//cnt是逆序总数 contri[i]表示数字i对逆序对数目的贡献 
inline int lowbit(int x){
	return x & -x;
}

inline void update(int pos,int num){//树状数组更新 
	for(int i=pos;i<=n;i+=lowbit(i)) c[i]+=num;
	return ;
}

inline int sum(int pos){//树状数组求和 
	int res=0;
	for(int i=pos;i>=1;i-=lowbit(i)) res+=c[i];
	return res;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		update(a[i],1);
		contri[a[i]]=sum(n)-sum(a[i]);//计算每个数的贡献=在它之前比它小的 
		cnt+=contri[a[i]];
	} 
	int ans=min(n-1,cnt);
	for(int i=1;i<n;i++){
		cnt-=contri[i];//删除数字1~n-1 
		ans=min(ans,cnt+i);
	}
	printf("%d\n",ans);
	return 0;
}