A9332 · Sereja and Brackets

题目描述

Sereja has a bracket sequence $s_{1},s_{2},...,s_{n}$ , or, in other words, a string $s$ of length $n$ , consisting of characters "(" and ")". Sereja needs to answer $m$ queries, each of them is described by two integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ . The answer to the $i$ -th query is the length of the maximum correct bracket subsequence of sequence $s_{li},s_{li}+1,...,s_{ri}$ . Help Sereja answer all queries. You can find the definitions for a subsequence and a correct bracket sequence in the notes. Sereja 有一个括号序列$s_{1},s_{2},...,s_{n}$ ，或者换句话说，一个长度为 n 的字符串 s ，由字符 "(" 和 ")" 组成。 Sereja 需要回答 m 个查询，每个查询由两个整数 li, ri 描述。 $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ .第 i 个查询的答案是序列 $s_{li},s_{li}+1,...,s_{ri}$ 的最大正确括号子序列的长度。帮助 Sereja 回答所有问题。 您可以在注释中找到子序列和正确括号序列的定义。

The first line contains a sequence of characters $s_{1},s_{2},...,s_{n}$ $(1<=n<=10^{6})$ without any spaces. Each character is either a "(" or a ")". The second line contains integer $m$ $(1<=m<=10^{5})$ — the number of queries. Each of the next $m$ lines contains a pair of integers. The $i$ -th line contains integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ — the description of the $i$ -th query. 输入 第一行包含字符 $s_{1},s_{2},...,s_{n}$ $(1<=n<=10^{6})$序列，不含空格。每个字符都是"("或")"。第二行包含整数 $m$ $(1<=m<=10^{5})$ - 查询次数。接下来的每行 m 都包含一对整数。第 i 行包含整数 $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ - i 次查询的描述。

Print the answer to each question on a single line. Print the answers in the order they go in the input. 输出 将每个问题的答案打印在一行上。按输入的顺序打印答案。

输入 #1

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

输出 #1