题解：P14419 [JOISC 2014] 有趣的家庭菜园 / Growing Vegetables is Fun

· · 题解

模拟赛 T4，被 T2 创飞根本没看倒闭倒闭倒闭倒闭，爽爽爽爽爽。

首先我们注意到最后的序列一定是呈一个单峰的样子。

然后发现对于需要单增的序列的交换次数为其逆序对数，单减序列相当于顺序对数。

然后我们考虑对于一个数 i ，是将其放在单增序列还是单减序列中，加上其顺、逆序对数即可。

使用树状数组维护，时间复杂度 O(n\log n)。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_Start;
constexpr int N=3*1e5+10;
int _=1,n,ans=0,cnt1=0,cnt2=0,a[N],p[N],q[N],c[N][2];
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}inline void files(){
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
}inline void clr(){
//  Don't Forget!

}int lowbit(int x){return x&(-x);}
void add(int x,int d,int opt){for(int i=x;i<N;i+=lowbit(i)) c[i][opt]+=d;}
int asks(int x,int opt){
    int cnt=0;
    for(int i=x;i>=1;i-=lowbit(i)) cnt+=c[i][opt];
    return cnt;
}
bool Test_MLE_End;
signed main(){
//  printf("%lf Mb\n",(&Test_MLE_End-&Test_MLE_Start-1)/1024.0/1024.0);
    files();
//  _=reads();
    while(_--){
        clr();n=reads();
        for(int i=1;i<=n;i++) p[i]=a[i]=reads();
        sort(p+1,p+n+1);int cnt=unique(p+1,p+n+1)-p-1;
        for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
        memset(p,0,sizeof(p));
        for(int i=n;i>=1;i--){
            p[i]=asks(n,1)-asks(a[i],1);
            add(a[i],1,1);
        }for(int i=1;i<=n;i++){
            q[i]=asks(n,0)-asks(a[i],0);
            add(a[i],1,0);ans=ans+min(q[i],p[i]);
        }printf("%lld\n",ans);
    }return 0;
}