Ơ trong 1 lần đi chơi với đám bạn (Khánh, Hòa, Khoa, Quân, Ngạn), cả 5 thanh niên này đều muốn chơi game, nhưng mà ai cũng không có tiền nhưng cạnh bên quán game lại có 1 cô gái tên là Thảo, cô gái này đưa ra nhưng bài toán, nếu giải được bài toán thì sẽ được thưởng 1 số tiền random(10K -> 100K), thế là 5 thanh niên này liền bắt tay vào giải bài toán để kiếm tiền chơi game. Nhưng bài toán quá khó, bạn có thể giải giúp 5 thanh niên này được không?
Cho 1 chuỗi kí tự S chỉ gồm kí tự '(' và ')' và m truy vấn, mỗi truy vấn là 2 số nguyên dương l,r (1≤l≤r≤S.size()).
Lưu ý: S.size() là số lượng kí tự của chuỗi S
Yêu cầu: Hãy xác định dãy ngoặc đúng dài nhất trong đoạn (l,r)
Input
- Dòng thứ nhất là chuỗi kí tự S (1≤S.size()≤106)
- Dòng thứ 2 là số nguyên dương m là số lượng truy vấn (1≤m≤105)
- m dòng tiếp theo là 2 số nguyên dương l,r (1≤l≤r≤S.size())
Output
- m dòng số nguyên dương , tương ứng với kết quả của đáp án
Sample input
Copy
(((())((((()()((((((()((()(((((((((((()((
6
20 37
28 32
12 18
7 25
21 33
4 5
Sample Output
Copy
4
0
2
6
4
2
Giải thích
- Trong truy vấn thứ 1 ta có chuỗi
((()((()(((((((((
, ta thấy chuỗi có dãy ngoặc đúng dài nhất là()()
. Vậy kết quả là 4
Giới hạn
- 1≤S.size(),m≤1000 tương ứng với 43.33% test
- 56.67% test còn lại không có ràng buộc gì thêm
Nguồn bài: Nguyễn Đức Nhã (Algorit).