Counting values inside ranges
National Olympiad — Regional round
Submission name: range.cpp
Problem summary
For each inclusive value interval [a,b], count the elements of the given array whose values lie in it. Equal elements at different positions count separately.
Input
n; n values; m; then m pairs a b.
Output
One count per query.
Constraints
0<n,m<100000; all values and query endpoints are positive and at most 100000; a≤b.
Worked example
An independently prepared example for this explanation.
Input
4 2 2 5 9 2 2 5 3 4
Output
3 0
Solution analysis
- Count each value, then build cumulative frequencies.
- Answer [a,b] by prefix[b]−prefix[a−1].
Why it works
The subtraction removes exactly those elements below a from those at most b.
Complexity: O(n+m+V) time and O(V) space, V=100000.
Watch out. Intervals refer to values, not array positions.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The subtraction removes exactly those elements below a from those at most b.
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,x,m;
cin>>n;
vector<int>p(100001);
while(n--){
cin>>x;
++p[x];
}
for(int i=1;i<=100000;i++){
p[i]+=p[i-1];
}
cin>>m;
while(m--){
int a,b;
cin>>a>>b;
cout<<p[b]-p[a-1]<<'\n';
}
}