Ant Greetings in a Subarray
National Olympiad — National round (2019 season)
Submission name: ants.cpp
Problem summary
Ants are indexed left to right. A + ant moves right and a − ant moves left. A greeting occurs exactly for a + before a −. Count greetings restricted to each [L,R] query.
Input
N, direction string, T, then T intervals.
Output
One greeting count per interval.
Constraints
2 ≤ N ≤ 100000; 1 ≤ T ≤ 10000.
Worked example
Input and output for the worked example discussed below.
Input
7 ++--+-- 3 1 4 3 4 4 7
Output
4 0 2
Solution analysis
- Precompute prefix counts of pluses,minuses and greeting pairs. At each minus, add the number of earlier pluses to the running pair count.
- pairs[R]−pairs[L−1] still includes pairs whose plus is before L and minus is inside [L,R]. Subtract plus[L−1]×(minus[R]−minus[L−1]) to remove exactly these pairs.
- The sample’s ++-- contains four pairs, -- contains none, and -+-- contains two. Opposite directions moving apart never meet.
Why it works
Each pair is counted once at its minus endpoint; the prefix correction removes exactly those with a plus before the queried interval.
Complexity: O(N) preprocessing and space, O(1) per query.
Watch out. Use long long for up to billions of pairs and include the crossing-prefix correction.
Commented C++17 solution
An independently written complete program with standard headers.
// Each pair is counted once at its minus endpoint; the prefix correction removes exactly those with a plus
// before the queried interval.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int count;
string directions;
cin>>count>>directions;
vector<long long>plus(count+1),minus(count+1),pairs(count+1);
for(int index=1;index<=count;index++){
plus[index]=plus[index-1];
minus[index]=minus[index-1];
pairs[index]=pairs[index-1];
if(directions[index-1]=='+'){
plus[index]++;
}
else{
minus[index]++;
pairs[index]+=plus[index-1];
}
}
int queries;
cin>>queries;
while(queries--){
int left,right;
cin>>left>>right;
cout<<pairs[right]-pairs[left-1]-plus[left-1]*(minus[right]-minus[left-1])<<'\n';
}
}