难以理解某人的源代码以解决 IOI 问题

Question

这是问题的 link：https://ioi2019.az/source/Tasks/Day1/Shoes/NGA.pdf

这里是关于问题陈述者t的简要解释：

给你一个整数 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 中的 add 和 query 函数是什么意思我只是对我在代码中注释的位置感到困惑到达底部的方式。我不明白它的作用和目的是什么。

有人可以解释这段代码的作用吗？或者就我应该如何 正确有效地 解决这个问题提出任何建议（甚至可能是你的解决方案？）。谢谢。

Answer 1

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

我们已经将一个鞋码的元组排序在一个<size, idx>的向量中，这意味着这个尺码的所有负片占据了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);

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

难以理解某人的源代码以解决 IOI 问题

Difficulty understanding someones source code to a solution of an IOI problem

c++

algorithm

std-pair