MOZHSLS - Sharmeen Loves Substring [ HARD ]

no tags 

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} and {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
mahabub618: 2023-01-25 22:15:51

It can be solved using Segment tree in online. Just keep store all possible substring of "sms". Be careful about using int instead of long long.
Time complexity: [ O(n log n) * merging complexity ]

Last edit: 2023-01-25 22:17:00
amir_quantom: 2022-09-06 12:47:23

Can be solved using MO algorithm easily

debsourav33: 2019-10-25 13:38:08

Did it online with segtree. A node is a 5 tuple contain the count of S, M, SM, MS and SMS.

julkas: 2018-09-10 22:04:47

Nice problem.

mehmetin: 2018-07-03 18:30:19

Accepted with O(1) per query, but the constant is somewhat high, I guess. Also, running too many loops during pre-processing.

Last edit: 2018-07-05 11:57:41
[Rampage] Blue.Mary: 2018-07-03 14:44:40

It's not hard to solve it online with segTree.

amulyagaur: 2018-07-02 06:48:44

Anyone did it online?

wisfaq: 2018-07-01 21:40:03

Great problem.

mehmetin: 2018-07-01 11:44:32

Is O(1) per query possible?


Added by:Avik Sarkar
Date:2018-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own