Ilya and Queries 313/B

Okay so this problem was honestly kind of funny to me at first. I read the input and had zero clue what l and r even meant. it was a range query on indexes of a string.

So in this problem you receive a string consisting of '#' and '.' only. For each query (l,r) you have to calculate number of positions i for which characters at positions i and i+1 are the same.

Well, in order to solve this problem you cannot just iterate over all positions i for each pair of l and r, since in such case time complexity becomes : O(n*m)which will guaranteed TLE given the constraints. So, you should come down to 0(n) or O(n log n)

And since you are dealing with range summing/counting, prefix sum technique just screams at you to use it. But wait ,you cannot use it straightforward with the original string, but there must be some precomputation first.

Here's where I made my first dumb mistake: I thought about representing # as 1 and . as 0 and then prefix summing that. That makes no sense, because the problem isn't asking about individual characters — it's asking about adjacent matching pairs.

therefore,precompute a hashsum array where each entry at index i tells you whether hash[i] and hash[i-1] are the same (1 if yes, 0 if no). This array has size n-1.

Approach

Traverse the string starting from index 1. For each position i, check if hash[i] == hash[i-1]. If yes, push 1. Otherwise, push 0. That builds your hashsum array.

String: #..### Characters at positions: 1 2 3 4 5 6

Adjacent pairs: (1,2) (2,3) (3,4) (4,5) (5,6) Matches: 0 1 0 1 1

hashsum = [0, 1, 0, 1, 1]

Then build a standard prefix sum array pref on top of hashsum.

pref = [0, 0, 1, 1, 2, 3]

For a query (l, r), the answer is pref[r-1] - pref[l-1]

CODE:

 #include<bits/stdc++.h>
using namespace std;
 
    typedef  long long     ll;
    
    typedef vector< long long    > VLL;
void solve();
int   main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    return 0;       
}
void solve() {
    string hash;
    cin >> hash;
    VLL hashsum;
    for (ll i = 1; i <= hash.size() - 1; i++)
    {
        if(hash[i]==hash[i-1]){
            hashsum.push_back(1);
        }
        else
            hashsum.push_back(0);//......    //1 1 1 1 1 -(1,2) (2,3) (3,4) (4,5) (5,6)       psum  0 1 0 1 1
    }                            //#..###   // 0 1 0 1 1  (1,2) (2,3) (3,4) (4,5) (5,6)         psum 0 1 1 2 3
    VLL pref(hashsum.size() + 1, 0);
    for (ll i = 1; i <= hashsum.size() ;i++){
        pref[i] = pref[i - 1] + hashsum[i - 1];
    }
    ll query;
    cin >> query;
    while(query--){
        ll l, r;
        cin >> l >> r;
        cout << pref[r - 1] - pref[l - 1]<<endl;
    }
}

Complexity

Preprocessing: O(n) Each query: O(1) Total: O(n + m)