Parenthesis String ?
Time limit0.5sMemory limit512 MB
Given a parenthesis string and range queries, output the sum over all queries of 1 if the queried substring is a correct parenthesis string, else 0.
- Level
Medium6 of 10
- Topics
- Stack, Prefix sum, Hash map, String matching
- Solved
- No attempts yet
Problem
A parenthesis string is a string consisting of ( and ), and a correct parenthesis string is defined as follows.
- The empty string is a correct parenthesis string.
- If S is a correct parenthesis string, then (S) is also a correct parenthesis string.
- If S and T are correct parenthesis strings, then ST is also a correct parenthesis string.
- Every correct parenthesis string can be built using only the three rules above.
You are given a parenthesis string S = s1s2...sN consisting of ( and ), along with M queries. Each query consists of two integers i and j (1 ≤ i ≤ j ≤ N), and means the following.
- 1 if the substring SiSi+1...Sj of S is a correct parenthesis string, and 0 otherwise
Run all queries and find the sum of their results.
Input
The first line gives the string S. The second line gives the number of queries M. The following M lines give one query per line.
Output
Print the sum of the query results.
Constraints
- 1 ≤ |S| ≤ 100,000
- 1 ≤ M ≤ 100,000