【C++】lower_boundとupper_boundを用いて区間に含まれる個数を求める

C++で整列済みの配列やvector等のコンテナにおいてある区間に含まれる個数をlower_bound、upper_boundを用いて求める方法を備忘録代わりに記します。

以下のコードではvectorを使用した場合を想定していますが、配列を用いる場合は
upper_bound(vector名.begin(), vector名,end(), value)、lower_bound(vector名.begin(), vector名,end(), value)をupper_bound(配列名, 配列名 + 配列の要素数, value)、lower_bound(配列名, 配列名 + 配列の要素数, value)に変更してください（ただしこれは探索範囲をvector（配列）の全範囲とする場合です）。

• $[a, b]$（$a$以上、$b$以下）

この場合は

upper_bound(vector名.begin(), vector名.end(), b) - lower_bound(vector名.begin(), vector名.end(), a)

とすればよいです。以下に例を示します。

#include <bits/stdc++.h>

using namespace std;

int main (int argc, char *argv[]) {
    vector<int> A; // A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> B; // B = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> C; // C = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]
    vector<int> D; // C = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]

    for (int i = 0; i < 11; ++i) {
        A.push_back(i);
        B.push_back(i);
        C.push_back(i);
        D.push_back(i);

        if (i == 2) {
            B.push_back(i);
            D.push_back(i);
        }

        if (i == 9) {
            C.push_back(i);
            D.push_back(i);
        }
    }

    cout << upper_bound(A.begin(), A.end(), 9) - lower_bound(A.begin(), A.end(), 2) << endl; // 8
    cout << upper_bound(B.begin(), B.end(), 9) - lower_bound(B.begin(), B.end(), 2) << endl; // 9
    cout << upper_bound(C.begin(), C.end(), 9) - lower_bound(C.begin(), C.end(), 2) << endl; // 9
    cout << upper_bound(D.begin(), D.end(), 9) - lower_bound(D.begin(), D.end(), 2) << endl; // 10

    return 0;
}

• $[a, b)$（$a$以上、$b$未満）

この場合は

lower_bound(vector名.begin(), vector名.end(), b) - lower_bound(vector名.begin(), vector名.end(), a)

とすればよいです。以下に例を示します。

#include <bits/stdc++.h>

using namespace std;

int main (int argc, char *argv[]) {
    vector<int> A; // A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> B; // B = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> C; // C = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]
    vector<int> D; // C = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]

    for (int i = 0; i < 11; ++i) {
        A.push_back(i);
        B.push_back(i);
        C.push_back(i);
        D.push_back(i);

        if (i == 2) {
            B.push_back(i);
            D.push_back(i);
        }

        if (i == 9) {
            C.push_back(i);
            D.push_back(i);
        }
    }

    cout << lower_bound(A.begin(), A.end(), 9) - lower_bound(A.begin(), A.end(), 2) << endl; // 7
    cout << lower_bound(B.begin(), B.end(), 9) - lower_bound(B.begin(), B.end(), 2) << endl; // 8
    cout << lower_bound(C.begin(), C.end(), 9) - lower_bound(C.begin(), C.end(), 2) << endl; // 7
    cout << lower_bound(D.begin(), D.end(), 9) - lower_bound(D.begin(), D.end(), 2) << endl; // 8

    return 0;
}

1. $(a, b]$（$a$より大きく、$b$以下）

この場合は

upper_bound(vector名.begin(), vector名.end(), b) - upper_bound(vector名.begin(), vector名.end(), a)

とすればよいです。以下に例を示します。

#include <bits/stdc++.h>

using namespace std;

int main (int argc, char *argv[]) {
    vector<int> A; // A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> B; // B = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> C; // C = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]
    vector<int> D; // C = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]

    for (int i = 0; i < 11; ++i) {
        A.push_back(i);
        B.push_back(i);
        C.push_back(i);
        D.push_back(i);

        if (i == 2) {
            B.push_back(i);
            D.push_back(i);
        }

        if (i == 9) {
            C.push_back(i);
            D.push_back(i);
        }
    }

    cout << upper_bound(A.begin(), A.end(), 9) - upper_bound(A.begin(), A.end(), 2) << endl; // 7
    cout << upper_bound(B.begin(), B.end(), 9) - upper_bound(B.begin(), B.end(), 2) << endl; // 7
    cout << upper_bound(C.begin(), C.end(), 9) - upper_bound(C.begin(), C.end(), 2) << endl; // 8
    cout << upper_bound(D.begin(), D.end(), 9) - upper_bound(D.begin(), D.end(), 2) << endl; // 8

    return 0;
}

• $(a, b)$（$a$より大きく、$b$より小さい）

この場合は

lower_bound(vector名.begin(), vector名.end(), b) - upper_bound(vector名.begin(), vector名.end(), a)

とすればよいです。以下に例を示します。

#include <bits/stdc++.h>

using namespace std;

int main (int argc, char *argv[]) {
    vector<int> A; // A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> B; // B = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    vector<int> C; // C = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]
    vector<int> D; // C = [0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]

    for (int i = 0; i < 11; ++i) {
        A.push_back(i);
        B.push_back(i);
        C.push_back(i);
        D.push_back(i);

        if (i == 2) {
            B.push_back(i);
            D.push_back(i);
        }

        if (i == 9) {
            C.push_back(i);
            D.push_back(i);
        }
    }

    cout << lower_bound(A.begin(), A.end(), 9) - upper_bound(A.begin(), A.end(), 2) << endl; // 6
    cout << lower_bound(B.begin(), B.end(), 9) - upper_bound(B.begin(), B.end(), 2) << endl; // 6
    cout << lower_bound(C.begin(), C.end(), 9) - upper_bound(C.begin(), C.end(), 2) << endl; // 6
    cout << lower_bound(D.begin(), D.end(), 9) - upper_bound(D.begin(), D.end(), 2) << endl; // 6

    return 0;
}