传送门

题意是说给定一个序列，只能交换相邻的两个数。问最后形成单峰序列（单调也是单峰）所需要的最小交换步数。

首先如果只需要单调数列，那么排序后，每个数在原序列中的下标所形成的逆序对就是交换次数。

由这个性质可以知道，旧序列的下标在新序列的逆序对就是答案。

接下来考虑如何形成单峰，做法是贪心，尽量形成少的逆序对。可以用树状数组动态维护。最开始的想法是说把尽量小的数往两边扔。但这样并没有很好的性质继续贪。
正确的做法是先考虑最大的数字。因为最终序列每个数字的相对位置都是固定的，所以先考虑最高的数字。

此时还需要发现一个性质：在一个序列（无论这个序列如何调整顺序）的两端加入一个数，所形成的新的逆序对/顺序对是固定的

也就是说，考虑第k大数字的时候的时候，只需要比较加在第k – 1大的数字的左边还是右边。由于k – 1大的数字所形成的序列是连续的，那么就等于在序列两端加数字，使得产生尽量少的逆序对。而在序列内部的数字如何调整对于要新加入的数字在左边还是右边是没有影响的。此时可以发现贪心策略是正确的。

对于值一样大的数字，由于相同的值最后肯定是相对顺序的，所以在考虑逆序对的时候不需要考虑和相同数字所产生的逆序对。具体来说，就是把所有一样的数字的结果先算出来，再把他们加入树状数组。

#include<bits/stdc++.h>
using namespace std;
const int maxn  = 3e5 + 233;
typedef long long ll;
typedef pair<int,int> pii;
vector<pii> a;
int n; 
int c[maxn];
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] += 1;
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int k; scanf("%d", &k);
        a.push_back({k, i});
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    // for(int i = 0; i < n; i++) cerr << a[i].second <<' '; puts("");
    ll ans = 0;
    for(int i = 0; i < a.size(); i++)
    {
        int p = i;
        while(p < a.size() && a[i].first == a[p].first)
        {
            int tmp = ask(a[p].second);
            ans += min(tmp, i - tmp);
            p++;
        }
        for(int j = i; j < p; j++) add(a[j].second);
        i = p - 1;
    }
    cout << ans;
}