Description：

给定一个长度为 $2n$ 的序列， $1\sim n$ 各出现两次，可以交换相邻两项，两个同样的数放在一起会对消，求把所有数对消的最小交换次数。

$1\leqslant n\leqslant 50000$

Solution：

分三种情况，如果是 $1\dots 1\dots 2\dots 2$ ，那么 $1$ 和 $2$ 一定不会相互影响，如果是 $1\dots 2\dots 1\dots 2$ 那他们之间必有一此交换，如果是 $1\dots 2\dots2\dots1$ ，那 $2$ 一定在 $1$ 之前先消，所以把所有对数拿出来按之间的距离排序，每次用树状数组统计两个之间还有多少没有被消掉的即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

struct seg

{

	int l,r;

	seg(){l = r = 0;}

}s[MAXN];

bool cmp_l(seg a,seg b){return a.r - a.l < b.r - b.l;}

int c[MAXN << 1];

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

void add(int p,int x){for(int i = p;i <= 2 * n;i += lowbit(i))c[i] += x;return;}

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

int main()

{

	scanf("%d",&n);

	int k;

	for(int i = 1;i <= n * 2;++i)

	{

		scanf("%d",&k);

		if(s[k].l == 0)s[k].l = i;

		else s[k].r = i;

		add(i,1);

	}

	sort(s + 1,s + 1 + n,cmp_l);

	int ans = 0;

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

	{

		add(s[i].l,-1);add(s[i].r,-1);

		ans += query(s[i].r) - query(s[i].l);

	}

	cout << ans << endl;

	return 0;

}