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 回答所有问题。
您可以在注释中找到子序列和正确括号序列的定义。
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 次查询的描述。
输入
第一行包含字符 $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
0 0 2 10 4 6 6
说明/提示
A subsequence of length $|x|$ of string $s=s_{1}s_{2}...\ s_{|s|}$ (where $|s|$ is the length of string $s$ ) is string $x=s_{k1}s_{k2}...\ s_{k|x|}$ $(1<=k_{1}<k_{2}<...<k_{|x|}<=|s|)$ .
A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
For the third query required sequence will be «()».
For the fourth query required sequence will be «()(())(())».
注
字符串$s=s_{1}s_{2}...\ s_{|s|}$ (其中 |s| 是字符串 s 的长度)的长度为 |x| 的 子序列是字符串$x=s_{k1}s_{k2}...\ s_{k|x|}$ $(1<=k_{1}<k_{2}<...<k_{|x|}<=|s|)$。
正确的括号序列是指可以通过在字符串的字符之间插入字符"1"和"+"来转换为正确的重音表达式的括号序列。例如，括号序列"()()", "(())" 是正确的(得到的表达式为"(1)+(1)"、"((1+1)+1)")，而")("和"("则不正确。
第三个查询所需的序列将是"()"。
第四个查询的必填序列是"()()()()) "。
A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
For the third query required sequence will be «()».
For the fourth query required sequence will be «()(())(())».
注
字符串$s=s_{1}s_{2}...\ s_{|s|}$ (其中 |s| 是字符串 s 的长度)的长度为 |x| 的 子序列是字符串$x=s_{k1}s_{k2}...\ s_{k|x|}$ $(1<=k_{1}<k_{2}<...<k_{|x|}<=|s|)$。
正确的括号序列是指可以通过在字符串的字符之间插入字符"1"和"+"来转换为正确的重音表达式的括号序列。例如，括号序列"()()", "(())" 是正确的(得到的表达式为"(1)+(1)"、"((1+1)+1)")，而")("和"("则不正确。
第三个查询所需的序列将是"()"。
第四个查询的必填序列是"()()()()) "。