题目大意

给定 $n$ 双鞋，要求通过相邻交换将鞋子排成合法排列（满足大小相同，左右位置 $2i$ 和 $2i+1$），求最少交换次数。

思路

相邻交换的次数等价于元素实际需要移动的距离减去已处理元素的个数。例如，若要将位置 $a$ 的鞋移到位置 $b$，中间有 $k$ 个未被处理的鞋，则需要 $k$ 次交换。

由于需要动态统计区间内未被处理的鞋的数量，考虑用树状数组维护前缀和。

我们先用 $pos$ 记录每个大小的鞋的位置，为避免负数下标，加上偏移量 $n$。

从右到左遍历所有鞋，若当前鞋未被处理，找到其配对鞋的位置。计算当前鞋与配对鞋之间的未处理鞋数，累加到答案。若当前鞋是左脚，说明右鞋在左侧，需要额外调整顺序（加 $1$ 次交换）。最后标记两只鞋为已处理，并在树状数组中移除。

code

#include<bits/stdc++.h>
#define int long long
#define N 2000005
using namespace std;

int sh[N];
bool p[N];
int t[N], n;
vector<int> pos[N];
int lowbit(int x){return x & -x;}
void add(int x, int k){
    while(x <= 2 * n){
        t[x] += k;
        x += lowbit(x);
    }
}
int get(int x){
    int ans = 0;
    while(x){
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    int total = 2 * n;
    for(int i = 1; i <= total; i++){
        cin >> sh[i];
        pos[sh[i] + n].push_back(i); 
        add(i, 1);
    }

    int ans = 0;
    for(int i = total; i >= 1; i--){
        if(p[i]) continue;
        p[i] = 1;
        int siz = sh[i];
        pos[siz + n].pop_back();
        int rr = pos[-siz + n].back();
        pos[-siz + n].pop_back();
        p[rr] = 1;
        add(rr, -1);
        ans += get(i - 1) - get(rr - 1);
        if(sh[i] < 0) ans++;
    }
    cout << ans << "\n";
    return 0;
}