问题描述
你现在有N对手套，但是你不小心把它们弄乱了，需要把它们整理一下。N对手套被一字排开，每只手套都有一个颜色，被记为0~N-1，你打算通过交换把每对手套都排在一起。由于手套比较多，你每次只能交换相邻两个手套。请你计算最少要交换几次才能把手套排整齐。
输入格式
输入第一行一个N，表示手套对数。
第二行有2N个整数，描述了手套的颜色。每个数都在0~N-1之间，且每个数字都会出现恰好两次。
输出格式
一行，包含一个数，表示最少交换次数。
样例输入
2
0 1 0 1
样例输出
1
数据范围
30%的数据N≤9；
60%的数据N≤1000；
100%的数据N≤200,000。
一开始不晓得怎么做，直接n²暴力过6组。后来才知道此题是重新编号然后归并排序求逆序对。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int a[400005],b[400005],r[400005];
int n,q;long long ans;
void f(int left,int right)
{
int m,i,j,k;
if(left==right)return ;
m=(left+right)>>1;
f(left,m);
f(m+1,right);
i=left;j=m+1;k=left;
while(i<=m&&j<=right)
{
if(a[i]<=a[j])
r[k++]=a[i++];
else
{
r[k++]=a[j++];ans+=j-k;
}
}
while(i<=m)r[k++]=a[i++];
while(j<=right)r[k++]=a[j++];
for(i=left;i<=right;i++)
a[i]=r[i];
}
int main()
{
freopen("gloves.in","r",stdin);
freopen("gloves.out","w",stdout);
scanf("%d",&n);//cin>>n;
for(int i=1;i<=n*2;i++)
{
scanf("%d ",&a[i]);//cin>>a[i];
if(b[a[i]]==0)
b[a[i]]=++q;
}
for(int i=1;i<=n*2;i++)
a[i]=b[a[i]];
f(1,2*n);
cout<<ans;
return 0;
}