Numbers in an interval
n numbers and q queries of the form L R are given (1 ≤ n, q ≤ 105). For every query print how many numbers are in the interval [L, R].
Example
Input
6
5 1 9 3 3 7
3
3 7
10 20
1 9Output
4
0
6The <algorithm> library has ready-made functions for binary search. With them, in one line you can find the first occurrence, the number of occurrences, the number of elements in an interval or the closest element – without mistakes with the bounds.
For a sorted array (or vector) and a value x:
| Function | Returns | Example: a = 1 3 3 3 7 9, x = 3 |
|---|---|---|
lower_bound(b, e, x) | the first element >= x | position 1 |
upper_bound(b, e, x) | the first element > x | position 4 |
binary_search(b, e, x) | true if x exists | true |
lower_bound and upper_bound return an iterator (a pointer to an element). We get the position by subtracting the beginning: lower_bound(v.begin(), v.end(), x) - v.begin(). If there is no such element, they return end(), that is, the position n.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> a = {1, 3, 3, 3, 7, 9};
int x = 3;
int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
int ub = upper_bound(a.begin(), a.end(), x) - a.begin();
cout << "the first >= 3 is at position " << lb << endl;
cout << "the first > 3 is at position " << ub << endl;
cout << "the number of threes: " << ub - lb << endl;
cout << "is there a 5? " << (binary_search(a.begin(), a.end(), 5) ? "yes" : "no") << endl;
cout << "lower_bound for 10: " << lower_bound(a.begin(), a.end(), 10) - a.begin() << endl;
return 0;
}
| Question | Expression (the array is sorted in ascending order) |
|---|---|
| How many elements are < x? | lower_bound(..., x) - a.begin() |
| How many elements are <= x? | upper_bound(..., x) - a.begin() |
| How many times does x appear? | upper_bound(..., x) - lower_bound(..., x) |
| How many elements are in [L, R]? | upper_bound(..., R) - lower_bound(..., L) |
| How many elements are >= x? | a.end() - lower_bound(..., x) |
For an ordinary array, instead of a.begin() and a.end() we write a and a + n.
For every query x we look for the element of the array closest to the number x. The candidates are the first element >= x (position p) and the element before it (position p − 1) – everything else is farther away.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
int main() {
int n, q;
cin >> n;
vector<int> a(n);
for (int &v : a) cin >> v;
sort(a.begin(), a.end());
cin >> q;
while (q--) {
int x;
cin >> x;
int p = lower_bound(a.begin(), a.end(), x) - a.begin();
int closest = -1;
if (p < n) closest = a[p]; // the first >= x
if (p > 0 && (closest == -1 || x - a[p - 1] <= closest - x)) closest = a[p - 1]; // the previous one (the smaller one at an equal distance)
cout << closest << "\n";
}
return 0;
}
5
1 4 9 15 20
3
6
12
254
9
20For 12 both 9 and 15 are at the distance 3, so the smaller one, 9, is printed.
lower_bound(b, e, x, greater<int>()) is used.lower_bound(v.begin(), v.end(), make_pair(x, -1)).set and map have their own methods s.lower_bound(x) – they are fast, while lower_bound(s.begin(), s.end(), x) on a set is slow (O(n)).Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
n numbers and q queries of the form L R are given (1 ≤ n, q ≤ 105). For every query print how many numbers are in the interval [L, R].
6
5 1 9 3 3 7
3
3 7
10 20
1 94
0
6n numbers (1 ≤ n ≤ 105) and a number S are given. How many pairs of positions i < j are there for which a[i] + a[j] <= S?
5 10
2 7 5 3 95a.begin().a[p] check that p < n – if the element you are looking for does not exist, p is n.1. What does lower_bound return for the value x?
2. How is the number of occurrences of x in a sorted array calculated?
3. What does lower_bound return if all the elements are smaller than x?