Equal Values to the Left and Right
National Olympiad — Municipal round (2018 season)
Submission name: red.cpp
Problem summary
For each queried position i, count values equal to a[i] strictly to its left and strictly to its right.
Input
N K, then N values, then K1-based queried positions.
Output
For each query, left and right equal-value counts.
Constraints
1 ≤ N ≤100000;0 ≤ a[i] ≤100000;1 ≤ K ≤10000.
Worked example
Input and output for the worked example discussed below.
Input
10 4 2 1 3 2 2 5 4 2 3 5 1 7 4 10
Output
0 3 0 0 1 2 1 0
Solution analysis
- Scan the sequence while maintaining frequency[value], the number of earlier occurrences. Before incrementing it for a[i], save that count as left[i].
- After the scan frequency[value] is its total number of occurrences. For a query i, right equals frequency[a[i]]−left[i]−1; the subtraction of1 excludes the queried element itself.
- In the sample, value2 occurs at positions1,4,5,8. Query4 therefore has one equal value on its left and two on its right. Query7 contains the unique value4, giving0 0.
Why it works
The forward counter before position i counts exactly equal values with smaller indices. The total occurrences partition into left, the current occurrence, and right, proving the subtraction formula. Thus each query is answered exactly.
Watch out. Store the earlier frequency before incrementing. Exclude the queried element and use1-based query indices.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int queries;
cin>>n>>queries;
vector<int>values(n+1);
vector<int>left(n+1);
vector<int>frequency(100001);
for(int i=1;i<=n;i++){
cin>>values[i];
// Save earlier occurrences before adding the current position.
left[i]=frequency[values[i]];
frequency[values[i]]++;
}
for(int query=0;query<queries;query++){
int index;
cin>>index;
int right=frequency[values[index]]-left[index]-1;
cout<<left[index]<<' '<<right<<'\n';
}
}