c++ - 难以理解某人的源代码来解决 IOI 问题

Question

这是问题的链接:https://ioi2019.az/source/Tasks/Day1/Shoes/NGA.pdf
这里是关于 的简要说明。问题陈述者吨:
给你一个整数 n 在 范围内1≤n≤1e5 这将表示数组中正整数的数量，以及数组中负整数的数量(因此数组的总大小将为 2n )。
问题希望您找到数组中所需的最小交换次数，使得数字的负值和该负数的绝对值彼此相邻( 使得 -x 位于 x 的右侧)
例子:
n = 2;
输入的数组 = {2, 1, -1, -2}
最少操作数为四:
2,1,-1,-2:0 次交换
2,-1,1,-2:1 次交换(交换 1 和 -1)
2,-1,-2,1:2 次交换(交换 1 和 -2)
2,-2,-1,1:3 次交换(交换 -1 和 -2)
-2,2,-1,1:4 次交换(交换 2 和 -2)
最终答案将是四个。
另一个例子:
输入的数组 = {-2, 2, 2, -2, -2, 2}
最小掉期为一。因为我们可以交换索引 2 和 3 的元素。
最终数组:{-2,2,-2,2,-2,2}

在做这个问题时，我得到了错误的答案，我决定在 git hub 上查看某人的源代码。
这是源代码:

#include "shoes.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;

struct bit{
    int tree[MAXN];
    void add(int x, int v){
        for(int i=x; i<MAXN; i+=i&-i) tree[i] += v;
    }
    int query(int x){
        int ret = 0;
        for(int i=x; i; i-=i&-i) ret += tree[i];
        return ret;
    }
}bit;


lint count_swaps(vector<int> s) {
    int n = sz(s) / 2;
    lint ret = 0;
    vector<pi> v;
    vector<pi> ord[MAXN];
    for(int i=0; i<sz(s); i++){
        ord[abs(s[i])].emplace_back(s[i], i);
    }
    for(int i=1; i<=n; i++){
        sort(ord[i].begin(), ord[i].end());
        for(int j=0; j<sz(ord[i])/2; j++){
            int l = ord[i][j].second;
            int r = ord[i][j + sz(ord[i])/2].second; //confusion starts here all the way to the buttom
            if(l > r){
                swap(l, r);
                ret++;
            }
            v.emplace_back(l + 1, r + 1);
        }
    }
    for(int i=1; i<=2*n; i++) bit.add(i, 1);
    sort(v.begin(), v.end());
    for(auto &i : v){
        ret += bit.query(i.second - 1) - bit.query(i.first);
        bit.add(i.first, -1);
        bit.add(i.second, -1);
    }
    return ret;
}

但是，我认为我不太了解这段代码。
我了解 的功能是什么添加和 查询 在 BIT 中，我只是对我一直到底部对代码的评论感到困惑。我不明白它的作用和目的是什么。
有人可以看看这段代码在做什么吗？或者对我应该如何提出任何建议正确有效解决这个问题(甚至可能是您的解决方案？)。谢谢你。

Answer 1

int r = ord[i][j + sz(ord[i])/2].second;

我们已经在 <size, idx> 的 vector 中对一种鞋码的元组进行了排序。 ，这意味着这个大小的所有底片都占据了 ord[i] 的前半部分，所有的积极因素都在下半年。

if (l > r){
  swap(l, r);
  ret++;
}

在我们按大小排序之后，每个对应对的索引可能不会以负数在正数之前排序。其中每一个都需要交换。

v.emplace_back(l + 1, r + 1);

插入 v对应尺码 i 的鞋的区间.

for(int i=1; i<=2*n; i++) bit.add(i, 1);
sort(v.begin(), v.end());

在我们的段和树中为鞋子的每个索引位置添加值 1。对鞋间隔进行排序。

for(auto &i : v){
  ret += bit.query(i.second - 1) - bit.query(i.first);

v中的每双鞋，需要的交换次数是它们之间剩下的鞋子数量，以段的总和表示。

bit.add(i.first, -1);
bit.add(i.second, -1);

从树上移除这双鞋，这样新的段总和就不会包括它们。我们可以这样做，因为鞋间隔是从左到右处理的，这意味着没有“内”鞋在外鞋之前被处理。