Description：

给出一个序列，求最少交换次数使得不存在一个数两边都有数比他大。

$1\leqslant n \leqslant3\times 10^5$

Solution：

看样例感觉是两边求逆序对然后合并，然而最大的数字也是可以移动的，换一种想法就是可以贪心，即先把最小的数放在左边或右边，取一个最小的，然后把这个数从原序列中删除，后面的部分继续用相同的方式处理，这样我们需要一个查询前缀 $/$ 后缀和以及删除操作的数据结构，树状数组就可以了。

还有就是可能有相同数字，但发现相同数字一定不会两两交换，也就是说相同数字之间不会对答案产生贡献，于是先把所有相同数字删除再一起统计。

Code：

#include

#include

#include

#include

#include

#include

using namespace std;

int n;

#define MAXN 300010

struct grass

{

	int h,p;

}g[MAXN];

bool cmp_h(grass a,grass b){return a.h < b.h;}

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

int cpre[MAXN],csuf[MAXN];

void addpre(int p,int x){for(int i = p;i <= n;i += lowbit(i))cpre[i] += x;return;}

void addsuf(int p,int x){for(int i = p;i >= 1;i -= lowbit(i))csuf[i] += x;return;}

int querypre(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += cpre[i];return res;}

int querysuf(int p){int res = 0;for(int i = p;i <= n;i += lowbit(i))res += csuf[i];return res;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&g[i].h);

	for(int i = 1;i <= n;++i)g[i].p = i;

	sort(g + 1,g + 1 + n,cmp_h);

	for(int i = 1;i <= n;++i)addpre(i,1);

	for(int i = 1;i <= n;++i)addsuf(i,1);

	long long ans = 0;

	int cnt = 0;

	for(int i = 1,j;i <= n;i = j)

	{

		for(j = i;j <= n && g[j].h == g[i].h;++j){addpre(g[j].p,-1);addsuf(g[j].p,-1);}

		for(j = i;j <= n && g[j].h == g[i].h;++j){ans += min(querypre(g[j].p),querysuf(g[j].p));}

	}

	cout << ans << endl;

	return 0;

}