MOZHSLS  Sharmeen Loves Substring [ HARD ]
After solving the problem “MOZHSLM” Sharmeen become familiar with subsequence and somehow become interested in substring. Instead of learning more about substring she started asking some ludicrous questions to Mozahid about substring. Become tired of answering Sharmeen’s ludicrous questions Mozahid gives Sharmeen another problem which is slightly harder than the previous one. Mozahid will give Sharmeen a string of lowercase English letters and some queries. In each query he will give her a substring of that string. Sharmeen has to answer how many different subsequence of ‘sms’ exists in that substring. Can you help Sharmeen solving this problem?
Input
Given a string of lowercase English letters of length N( 1 <= N <= 10^5 ) in first line. In the second line given an integer Q( 1 <= Q <= 10^5 ), which is the number of queries. In each query you will be given two integer L , R ( 1 <= L <= R <= N ). L is the starting position of the substring and R is the ending position of the substring( 1 based position ).
Output
For each query you have to output an integer in one line which is the number of different subsequence of ‘sms’ in that substring.
N.B. Substring is a consecutive sequence of characters of a string. Where subsequence not necessarily need to be consecutive. But for both you have to maintain the order. For clearance ‘skmjssm’ has 2 different subsequence of ‘sms’. {1,3,5} & {1,3,6} ( 1 based position ). For better understanding see the sample input output.
Example
Input:sasmasamsas
3
1 6
3 9
8 11 Output:2
4
0
[ This problem originally written by MD. Mozahidul Islam Bhuiyan(kissu_pari_na) ]
hide comments
julkas:
20180910 22:04:47
Nice problem. 

mehmetin:
20180703 18:30:19
Accepted with O(1) per query, but the constant is somewhat high, I guess. Also, running too many loops during preprocessing.


[Rampage] Blue.Mary:
20180703 14:44:40
It's not hard to solve it online with segTree. 

amulyagaur:
20180702 06:48:44
Anyone did it online? 

wisfaq:
20180701 21:40:03
Great problem. 

mehmetin:
20180701 11:44:32
Is O(1) per query possible? 

kushwah121:
20180630 12:07:21
Last edit: 20180701 14:47:47 
Added by:  Avik Sarkar 
Date:  20180622 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 