题目链接：https://csacademy.com/contest/arhiva/#task/swap_pairing/
大意是给2*n个包含n种数字，每种数字出现恰好2次的数列，每一步操作可以交换相邻的两个数字，问最少需要操作多少次，可以使得所有的同种数字都相邻。
我的做法是考虑不同的数对的数字在原来数列中的位置关系，有三大类，如果我们用[]和{}表示的话就是：
[]{}
[{]}
[{}]
这三种位置情况。
第一种情况对答案的贡献应当是0。
第二种情况对答案的贡献应当是1。
第三种情况对答案的贡献应当是2。
接下来问题就是如何统计。我的方法是先计算所有的pair对，
总共n种数字，那么数对的个数就是(n-1)*n/2。
接下来需要减去第一种情况的个数，再加上第三种情况的个数。
第一种情况的统计应当是比较简单的，第三种情况可以规约到求某个线段内部有多少线段的问题。
统计可以用BIT来维护。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <set>
using namespace std; const int N=;
int a[N];
map<int,int> le;
map<int,int> ri; pair<int,int> pos[N];
int v[N];
int lowbit(int x) {
return x & -x;
}
int get(int x) {
int ret=;
while (x) {
ret+=v[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int add) {
while (x<N) {
v[x]+=add;
x+=lowbit(x);
}
}
int main () {
int n;
while (scanf("%d",&n)!=EOF) {
memset(v,, sizeof(v));
le.clear();
ri.clear();
for (int i=;i<=n;i++) {
scanf("%d",a+i);
if (le[a[i]]==)
le[a[i]]=i;
else ri[a[i]]=i;
}
int cnt=;
for (map<int,int>::iterator it=le.begin();it!=le.end();it++) {
int key=it->first;
int val1=it->second;
int val2=ri[key];
pos[cnt].first=val1;
pos[cnt++].second=val2;
}
sort(pos+,pos+cnt);
int tot=n/;
long long ret=(tot-)*1LL*tot/2LL;
for (int i=tot;i>=;i--) {
int l=pos[i].first;
int r=pos[i].second;
ret+=get(r);
add(r,);
}
memset(v,,sizeof v);
for (int i=;i<=tot;i++) {
int l=pos[i].first;
int r=pos[i].second;
ret-=get(l);
add(r,);
}
cout<<ret<<endl; }
}
题解给了另一种做法，可以有一种最优解第一个数字不用移动，则接下来所有数字怎么移动都被固定了，中间仍然是用BIT来维护。