lower_boundとupper_boundの処理を知りたい。

Question

前提

以下のプログラムにおけるAjとCjをプログラムを作成する過程で見たいと思い出力したところ、自分の予想とは違かったので、どういう処理なのかを知りたいです。

該当のソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<long long> a(N), b(N), c(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    for (int i = 0; i < N; ++i) cin >> c[i];

    // ソートする
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    // b[j] を固定して考える
    long long res = 0;
    for (int j = 0; j < N; ++j) {
        long long Aj = lower_bound(a.begin(), a.end(), b[j]) - a.begin();
        cout << "lower_bound=" << *lower_bound(a.begin(), a.end(), b[j]) << endl;
        cout << "a.begin=" << *a.begin()  << endl;
        cout << "Aj=" << Aj << endl;
        long long Cj = N - (upper_bound(c.begin(), c.end(), b[j]) - c.begin());
         //cout << "N=" << N << endl;
         //cout << "upper_bound=" << *upper_bound(c.begin(), c.end(), b[j]) << endl;
         //cout << "Cj=" << Cj << endl;
        res += Aj * Cj;
    }
    cout << res << endl;
}

入力

3
1 1 1
2 2 2
3 3 3

出力結果

lower_bound=33
a.begin=1
Aj=3
lower_bound=33
a.begin=1
Aj=3
lower_bound=33
a.begin=1
Aj=3
27

プログラム上だと、 long long Aj = lower_bound(a.begin(), a.end(), b[j]) - a.begin();
なので、Aj＝33－1＝３２じゃないのでしょうか。
また、なぜ、ずっと33なのでしょうか...

試したこと

Aj、lower＿boundを出力。

補足情報（FW/ツールのバージョンなど）

些細なことでもコメント、ご指摘いただけると助かります...

Comments

[int32_t]

> ひとつ目の出力は、Aj=３、Cj＝56　となる予想でした。

入力データが不明なので、なぜこの予想なのか理解できません。

Answer 1

lower_bound(a.begin(), a.end(), b[j])

a は3要素ぜんぶ 1 で、b[j] は 2 です。aの指定範囲に2以上の値はありませんから、この lower_bounds() は a.end() を返します。33 というのは a.end() が指している値で、おそらくメモリ上のゴミでしょう。

Answer 2

ソートされた列に要素を挿入する(しかも挿入後もソートされた状態を保つ)とき、
lower_bound/upper_bound はそれぞれ挿入位置の最小/最大を返します。

たとえば列: 1, 2, 3, 3, 3, 4, 5 があり、要素3を挿入するとき、　挿入位置を|で表すと
最小位置(lower_bound)は 1, 2, |3, 3, 3, 4, 5
最大位置(upper_bound)は 1, 2, 3, 3, 3, |4, 5
両者に挟まれた範囲は要素3が存在する範囲となります。
※ 両者が等しいときは、列内に要素3が存在しないことを意味します。