Asia Yokohama Regional Contest 2018 G题 What Goes Up Must Come Down

链接 G题 https://codeforces.com/gym/102082

使其成为单峰序列需要交换多少次相邻的数。

树状数组维护逆序对。

对于每个序列中的数，要么在单峰的左侧，要么在单峰的右侧，所以从左边开始维护每个数相对于左侧的逆序对数量，从右边开始维护每个数相对于右侧的逆序对数量。取小加入答案即可。

 #include <bits/stdc++.h>

 #define debug(x) cout << #x << ": " << x << endl

 using namespace std;

 typedef long long ll;

 const int MAXN=1e5+;

 const int INF=0x3f3f3f3f;

 const int MOD=1e9+;

 int a[MAXN],L[MAXN],R[MAXN];

 struct BIT

 {

     int c[MAXN];

     void init() {memset(c,,sizeof(c));}

     int lowbit(int x) {return x&(-x);}

     void add(int i,int x)

     {

         while(i<MAXN)

         {

             c[i]+=x;

             i+=lowbit(i);

         }

     }

     ll sum(int i)

     {

         ll res=;

         while(i)

         {

             res+=c[i];

             i-=lowbit(i);

         }

         return res;

     }

 }tree;

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     int n;

     cin>>n;

     for(int i=;i<=n;++i) cin>>a[i];

     for(int i=;i<=n;++i)

     {

         tree.add(a[i],);

         L[i]=i-tree.sum(a[i]);

     }

     tree.init();

     for(int i=n;i>=;--i)

     {

         tree.add(a[i],);

         R[i]=n-i+-tree.sum(a[i]);

     }

     ll ans=;

     for(int i=;i<=n;++i)

         ans+=min(L[i],R[i]);

     cout<<ans<<endl;

     return ;

 }