Consecutive Segments
Description
Karel the Robot is given a string $S$ and $Q$ queries. The $i$th query consists of integers $L_i$ and $R_i$, with $1≤L_i≤R_i≤|S|$. Help Karel find the number of substrings of the same character in $S[L_i,R_i]$. For example, $aa$ contains one substring of the same character, $aba$ contains three, and $abbcccddaa$ contains five.
Line 1: One string, $S$.
Line 2: One integer, $Q$.
Lines 3…$Q+2$: Line $i+2$ contains integers $L_i$ and $R_i$, separated by a space.
Lines 1…$Q$: Line $i$ contains the answer to the $i$th query, more specifically the number of substrings of the same character in $S[L_i,R_i]$.
Input
Line 1: One string, $S$.
Line 2: One integer, $Q$.
Lines 3…$Q+2$: Line $i+2$ contains integers $L_i$ and $R_i$, separated by a space.
Output
Lines 1…$Q$: Line $i$ contains the answer to the $i$th query, more specifically the number of substrings of the same character in $S[L_i,R_i]$.
aabcccab
8
1 1
1 2
1 3
1 4
1 5
1 8
2 4
4 6
1
1
2
3
3
5
3
1
Note
$1≤S≤10^5$
$1≤Q≤10^5$
One-indexing is used in this problem. For example, if $S$=$aabcccab$, then $S[3,6]$=$bccc$, not $ccca$.
The substrings that the inputs correspond to are $a$,$aa$,$aab$,$aabc$,$aabcc$,$aabcccab$,$abc$, and $ccc$, respectively. For instance, the answer to the $5$th query is 3 because $aabcc$ contains three substrings of the same character: $aa$, $b$, and $cc$.