最后数列一定是单峰的，问题就是最小化最后的位置序列的逆序对数。
从大到小加数，每次贪心看放左边和右边哪个产生的逆序对数更少，树状数组即可。
由于大数放哪对小数不产生影响，所以正确性显然。
注意相同数之间一定能不构成逆序对，需要特判。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long long ll; 6 using namespace std; 7 8 const int N=300010; 9 ll ans; 10 int n,c[N],a[N],p[N]; 11 12 bool cmp(int x,int y){ return a[x]>a[y]; } 13 void add(int x,int k){ for (; x<=n; x+=x&-x) c[x]+=k; } 14 int que(int x){ int res=0; for (; x; x-=x&-x) res+=c[x]; return res; } 15 16 int main(){ 17 freopen("bzoj4240.in","r",stdin); 18 freopen("bzoj4240.out","w",stdout); 19 scanf("%d",&n); 20 rep(i,1,n) scanf("%d",&a[i]),p[i]=i; 21 sort(p+1,p+n+1,cmp); 22 for (int i=1; i<=n; ){ 23 int j=i; 24 for (; j<=n; j++){ 25 int x=que(p[j]); ans+=min(x,i-1-x); 26 if (a[p[j]]!=a[p[j+1]]) break; 27 } 28 for (; i<=j; i++) add(p[i],1); 29 } 30 printf("%lld ",ans); 31 return 0; 32 }