c++ - 要素の位置を取得する

Question

次の問題を解決したいと思います: n 要素のベクトルが与えられた場合、挿入ソート アルゴリズムがソートする必要があるスワップの数を見つけます。

例:
n = 5
2 1 3 1 2
答え: 4

説明（挿入ソートアルゴリズムのステップバイステップ）：
initialy：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 ループ)
次に、現在の数よりも小さい要素の数をカウントし、それらをカウンターに追加します。この要素をセットから削除します。(2番目の for ループ)

ご覧のとおり、問題は線形の複雑さを持つ std::distance原因セットに双方向イテレータがあることです。独自のツリーを実装せずに 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;
}