问题描述
你现在有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。
这道题题目看错，吐血~~我以为是求多少次把手套从大到小排好序~~
这题就是先考虑一下贪心做法——每次找到一对手套的前半只，把后半只换到它后面，不会对原序列其他数产生影响
这样我们可以O（n）确定一下每只手套的最终位置（全部靠前放，就是把后面那只放到前面那只的后面）
然后其实这样的操作的总数就是求逆序对数
所以重新编号+逆序对就可以A啦！
命题：上述操作的次数等于重新编号后数组的逆序对个数
引理：先对哪对手套进行操作并不影响答案（口糊见上）
证明：我们先把剩余数组中重新编号最小那对手套换完。所以我们只需要交换那后半只手套到第二的位子就可以了
要交换的次数是原序列中编号<后半只手套 且 重新编号后编号>这对手套的
得证啦！
#include<iostream> #include<algorithm> #include<cstdio> #define lowbit(x) x&(-x) #define N 400005 using namespace std; #define ll long long ll ans,n,i,bianhao[N],b[N],x,tree[N]; bool flag[N]; void update(ll u) { for(ll j=u;j<=n;tree[j]++,j+=lowbit(j)); } ll getsum(ll u) { ll tot=0; for(ll j=u;j;tot+=tree[j],j-=lowbit(j)); return tot; } int main() { ios::sync_with_stdio(false); cin>>n; n*=2; ll q=0; for(ll i=1;i<=n;i++) { cin>>x; if(!flag[x]) { flag[x]=1; bianhao[x]=++q; } b[i]=bianhao[x]; } for(ll i=n;i>=1;i--) { ans+=getsum(b[i]-1); update(b[i]); } cout<<ans<<endl; return 0; }