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

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

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

树状数组维护逆序对。

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

 1 #include <bits/stdc++.h>
 2 #define debug(x) cout << #x << ": " << x << endl
 3 using namespace std;
 4 typedef long long ll;
 5 const int MAXN=1e5+7;
 6 const int INF=0x3f3f3f3f;
 7 const int MOD=1e9+7;
 8 int a[MAXN],L[MAXN],R[MAXN];
 9 
10 struct BIT
11 {
12     int c[MAXN];
13     void init() {memset(c,0,sizeof(c));}
14     int lowbit(int x) {return x&(-x);}
15     void add(int i,int x)
16     {
17         while(i<MAXN)
18         {
19             c[i]+=x;
20             i+=lowbit(i);
21         }
22     }
23     ll sum(int i)
24     {
25         ll res=0;
26         while(i)
27         {
28             res+=c[i];
29             i-=lowbit(i);
30         }
31         return res;
32     }
33 }tree;
34 
35 int main()
36 {
37     ios::sync_with_stdio(false);
38     cin.tie(0);
39     int n;
40     cin>>n;
41     for(int i=1;i<=n;++i) cin>>a[i];
42     for(int i=1;i<=n;++i)
43     {
44         tree.add(a[i],1);
45         L[i]=i-tree.sum(a[i]);
46     }
47     tree.init();
48     for(int i=n;i>=1;--i)
49     {
50         tree.add(a[i],1);
51         R[i]=n-i+1-tree.sum(a[i]);
52     }
53     ll ans=0;
54     for(int i=1;i<=n;++i)
55         ans+=min(L[i],R[i]);
56     cout<<ans<<endl;
57     return 0;
58 }

View Code