BZOJ4240: 有趣的家庭菜园

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4240

Solution

今天模拟赛爆炸呀。
这题基本上所有人爆10。
天真地以为前缀做一遍逆序对再后缀做一遍，枚举中间点。
这其实是没看清题目。
每个点只要考虑使左边满足或右边满足所需的步数。
说白了就是找出每个点前面和后面有各多少数比它大。
这可以用树状数组求。
最后每个点贪心选往左移或右移，取最小值就行了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 300005
#define inf 100000000000
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
ll n,a[N],b[N],c[N],f[N],g[N],ans;
void add(ll x){ for (;x;x-=x&-x) c[x]++; }
ll get(ll x){ ll ans=0; for (;x<=n;x+=x&-x) ans+=c[x]; return ans; }
int main(){
    n=read(); for (ll i=1;i<=n;i++) b[i]=a[i]=read(); 
    sort(b+1,b+1+n);
    for (ll i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    for (ll i=1;i<=n;i++){ add(a[i]); f[i]=get(a[i]+1); } 
    memset(c,0,sizeof c);
    for (ll i=n;i;i--){ add(a[i]); g[i]=get(a[i]+1); }
    for (ll i=1;i<=n;i++) ans+=min(f[i],g[i]);
    write(ans);
}