What Goes Up Must Come Down

题意：
给你一个长度为n的序列，使序列呈先升序再降序的最少操作次数为多少？每次操作可以交换相邻的两个数。

思路：
对于每一个数来说，它最终要么左边的数全比它小，要么右边的数全比他小，每次移动相邻两个位置，所以你只需要判断它左边比它大的数的个数和右边比它大的个数的最小值（哪边小与那边大于它的交换），用树状数组统计大于它的个数(由于数状数组计算的是比它小的个数，所以你可以一开始就将数组内数的大小颠倒，则比它小的个数即为比它大的数)。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N=5e5+5;

int a[100005], t1[100005], inf=100004;

void add(int x,int d)
{
    while(x<=100004)
    {
        t1[x]+=d;
        x+=(x&(-x));
    }
}

int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=t1[x];
        x-=(x&(-x));
    }
    return sum;
}

int mi[100005];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        a[i]=inf-a[i];
    }
    memset(t1,0,sizeof(t1));
    for(int i=0;i<n;i++)
    {
        //printf("%d\n",sum(a[i]));
        mi[i]=sum(a[i]-1);
        add(a[i],1);
    }
    memset(t1,0,sizeof(t1));
    for(int i=n-1;i>=0;i--)
    {
        mi[i]=min(sum(a[i]-1),mi[i]);
        add(a[i],1);
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        ans=ans+mi[i];
    }
    cout << ans << endl;
    return 0;
}