Words in a Range
National Olympiad — Regional round
Submission name: words.cpp
Problem summary
Split a string over a, b and c into maximal nondecreasing runs. For each queried substring, report the number of runs it contains; its first character begins a run regardless of the character immediately outside the query.
Input
The string; query count K; then K pairs i j using one-based inclusive indices.
Output
One run count per query.
Constraints
String length and maximum word length are at most 20000; 1 ≤ K ≤ 100000; 1 ≤ i ≤ j ≤ string length. There is no separate maximum-length input.
Worked example
An independently prepared example for this explanation.
Input
abbcaac 3 1 7 4 6 5 7
Output
2 2 1
Solution analysis
- A new run begins exactly at a strict decrease between adjacent letters.
- Precompute prefix counts of these boundaries.
- For [i,j], answer one plus the number of decreases whose right endpoint is between i+1 and j.
Why it works
Inside any run letters never decrease; every decrease forces a new run. Thus the boundary count plus one is exact.
Watch out. Subtract the boundary at the left edge: it belongs outside the substring.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Inside any run letters never decrease; every decrease forces a new run. Thus the boundary
// count plus one is exact.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin>>s;
int n=s.size();
vector<int>p(n+1);
for(int i=1;i<=n;i++){
p[i]=p[i-1]+(i>1&&s[i-1]<s[i-2]);
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<1+p[r]-p[l]<<'\n';
}
}