C++
競技プログラミング

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;
}