c++ - 设置获取元素的位置

Question

我想解决以下问题:给定一个包含 n 个元素的 vector ，求插入排序算法需要排序的交换次数。

例如:
n = 5
2 1 3 1 2
答案:4

说明(插入排序算法一步一步):
初始值:2 1 3 1 2
1 2 3 1 2 ; 1交换1(1向左)
1 2 3 1 2 ; 0 交换
1 1 2 3 2 ; 2 互换(1 左 2 位置)
1 1 2 2 3 ; 1 交换(2 离开 1 个位置)

我的解决方案

我将每个项目的位置保留在初始数组中，以便稍后根据值和位置从集合中删除。(第一个 for 循环)
然后我计算小于当前数量的元素数量，将它们添加到计数器中并从集合中删除该元素。 (第二个 for 循环)

如您所见，问题在于 std::distance 具有 linear complexity原因集有双向迭代器。如何在不实现自己的树的情况下获得 O(1) 的复杂度？

int count_operations(vector<int> &v)
{
    set<pair<int, int>> s;
    // O(N * logN)
    for(int i = 0; i < (int) v.size(); ++i)
    {
        s.insert(make_pair(v[i], i));
    }
    int cnt = 0;
    // desired: O(N * log N) ; current O(N^2)
    for(int i = 0; i < (int) v.size(); ++i)
    {
        auto item = make_pair(v[i], i);
        auto it = s.find(item);
        int dist = distance(s.begin(), it);//O(N); I want O(1)
        s.erase(it);
        cnt += dist;
    }
    return cnt;
}

Answer 1

问题是获取集合中每个元素的排名，这可以使用顺序统计树(使用 gnu libc++ 中的 pbds 库)完成，如下所示。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <utility>
using namespace std;
using namespace __gnu_pbds;

typedef tree<
    pair<int, int>, /* key type */
    null_mapped_type, /* value type */
    less< pair<int, int> >, /* comparison */
    rb_tree_tag, /* for having an rb tree */
    tree_order_statistics_node_update> order_set;

int count_ops(std::vector<int> &v)
{
    order_set s;
    int cnt = 0;
    /* O(N*log(N)) */
    for(int i = 0; i < v.size(); i++)
        s.insert(pair<int, int>(v[i], i));
    for(int i = 0; i < v.size(); i++)
    {
        /* finding rank is O(log(N)), so overall complexity is O(N*log(N)) */
        cnt += s.order_of_key(pair<int, int>(v[i], i));
        s.erase(pair<int, int>(v[i], i));
    }
    return cnt;
}