C++ STLのsetを使って、右側にある小さい要素の個数を求める方法

このチュートリアルでは、C++ STLの std::set を使用して、配列内の各要素より右側に存在する小さい要素の個数を求めるプログラムについて解説します。

入力として整数の配列が与えられます。私たちのタスクは、新しい配列を作成し、その各位置に「現在の要素より右側にある、現在の要素より小さい要素の数」を格納することです。

アルゴリズムの考え方

std::set は要素を自動的にソートされた状態で保持する連想コンテナです。この性質を利用すると、次の手順で効率的にカウントできます。

1. 配列を右端から左へ向かって走査する。
2. 走査中の各要素を set に挿入する（この時点で set には「その要素以降（右側）の値」だけが格納されている）。
3. lower_bound() で「現在の要素以上となる最初の位置」のイテレータを取得し、distance() で先頭からの距離を求める。この距離が、まさしく「現在の要素より小さい要素の個数」に相当します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

void count_Rsmall(int A[], int len){
    set<int> s;
    int countSmaller[len];
    for (int i = len - 1; i >= 0; i--) {
        s.insert(A[i]);
        auto it = s.lower_bound(A[i]);
        countSmaller[i] = distance(s.begin(), it);
    }
    for (int i = 0; i < len; i++)
        cout << countSmaller[i] << " ";
}

int main(){
    int A[] = {12, 1, 2, 3, 0, 11, 4};
    int len = sizeof(A) / sizeof(int);
    count_Rsmall(A, len);
    return 0;
}

出力

6 1 1 1 0 1 0

処理の流れを確認しよう

入力 {12, 1, 2, 3, 0, 11, 4} の場合、結果は次のように対応しています。

• 12：右側の要素 1, 2, 3, 0, 11, 4 のすべてが12未満 → 6
• 1：右側で1未満ののは 0 のみ → 1
• 2：右側で2未満のは 0, 1 → ただし重複は set に格納されないため → 1
• 3：右側で3未満のは 0, 1, 2 → 重複除外後 → 1
• 0：右側に0未満の要素はない → 0
• 11：右側で11未満のは 4 のみ → 1
• 4：右側に要素なし → 0

なお、std::set は同一の値を保持しないため、配列内に重複した値が存在する場合、その分はカウントされない点に注意してください。

計算量について

set への挿入（insert）と位置探索（lower_bound）は、それぞれ O(log n) の計算量で実行できます。全要素を一度ずつ処理するため、全体としては単純な二重ループによる O(n²) の素朴な手法と比べて大幅に高速に動作します。