题解：P14899 [ICPC 2018 Yokohama R] What Goes Up Must Come Down

fish_love_cat · 2026-01-05 01:49:03 · 题解

简单题。

最后的数列是单峰的。

每个点显然要么在左边的坡上，要么在右边的坡上。

如果在左边的坡上，那么它左边的所有比它大的点都要与它交换。右边坡上同理。

于是正反各用树状数组对每个点求一遍以它为发端的逆序对数量即可得到每个点的每个选择的代价。

显然每个点取最优的代价进行选择，所有代价之和即为答案。

时间复杂度 O(n\log n)，做完了。

#include<bits/stdc++.h>
#define int long long
#define N 100000
#define lowbit(x) x&(-x)
using namespace std;
int a[100005];
int qz[100005];
int hz[100005];
int tr[100005];
int top;
void upd(int x){
    for(int i=x;i<=N;i+=lowbit(i))
    tr[i]++;
    top++;
}
int qry(int x){
    int ans=top;
    for(int i=x;i;i-=lowbit(i))
    ans-=tr[i];
    return ans;
}
signed main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    cin>>a[i],qz[i]=qry(a[i]),upd(a[i]);
    memset(tr,0,sizeof tr);top=0;
    for(int i=n;i;i--)
    hz[i]=qry(a[i]),upd(a[i]);
    for(int i=1;i<=n;i++)
    ans+=min(qz[i],hz[i]);
    cout<<ans;
    return 0;
}
//「喂！不是跟你说很多次很危险，不能乱爬吗！」

// 可蓉把几年前自己做过的事情全力拋到一边，如此训斥著莉艾儿。
// 要是被同辈以上的妖精或妮戈兰听到，一定会回她一句：「你有资格说别人吗？」