http://www.lydsy.com/JudgeOnline/problem.php?id=4240 我们的4.12模拟赛T1 和找逆序对差不多。。。 把序列变成合唱队形差不多就行了 一开始的想法是直接左边逆序对数和右边正序对数合并找最小 这样只有10分QAQ。。。 正确的思路是直接找数i在前面的逆序对数和后面的正序对数取小累加 用树状数组维护一下，时间复杂度O(nlogn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline ll read(){ ll k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } ll n,a[400001],b[400001],f[400001],c[400001]; ll m1[400001],m2[400001]; inline ll erfen(ll x,ll sum){ ll l=1,r=sum; while(l<=r){ ll mid=(l+r)>>1; if(b[mid]==x)return mid; if(b[mid]>x)r=mid-1; else l=mid+1; } return 0; } inline ll lowbit(ll x){return x&-x;} inline void add(ll x,ll v){for(ll i=x;i<=n;i+=lowbit(i))f[i]+=v;} inline ll sum(ll x){ll ans=0;for(ll i=x;i;i-=lowbit(i))ans+=f[i];return ans;} int main() { n=read();ll s=1; ll p=sqrt(n); for(ll i=1;i<=n;i++)c[i]=a[i]=read(); sort(c+1,c+n+1); b[1]=c[1]; for(ll i=2;i<=n;i++)if(c[i]!=c[i-1])s++,b[s]=c[i]; for(ll i=1;i<=n;i++)a[i]=erfen(a[i],s); memset(f,0,sizeof f);ll ans=0; for(ll i=1;i<=n;i++){ add(a[i],1); ans=i-sum(a[i]);m1[i]=ans; } memset(f,0,sizeof f);ans=0; for(ll i=n;i;i--){ add(a[i],1); ans=n-i+1-sum(a[i]);m2[i]=ans; } ans=0; for(ll i=1;i<=n;i++)ans+=min(m1[i],m2[i]); printf("%lld",ans); return 0; }