← 返回题目列表

Codeforces · 1593/G

G. 更换括号

中文机器翻译题面 查看原题

给出了一系列圆括号和方括号。您可以通过以下操作更改顺序:

1. 在不改变括号形式的情况下,将括号的方向从左括号改为右括号,反之亦然:即可以将 '(' 更改为 ')',')' 更改为 '(';可以将 '[' 更改为 ']',']' 更改为 '['。该操作需要花费 $$$0$$$ burles。
2. 将任何方括号更改为具有相同方向的圆括号:即,您可以将 '[' 更改为 '(',但不能将 '(' 更改为 '[';同样,您可以将 ']' 更改为 ')',但不能将 ')' 更改为 ']'。手术费用为$$$1$$$ burle。

这些操作可以按任意顺序执行任意次数。

给您一个长度为 $$$n$$$ 的字符串 $$$s$$$ 和类型为“l r”的 $$$q$$$ 查询,其中 $$$1 \le l < r \le n$$$。对于每个子串 $$$s[l \dots r]$$$,找到使其成为正确括号序列所需的最小成本。保证子串 $$$s[l \dots r]$$$ 的长度为偶数。

查询必须独立处理,即问题 $$$i$$$ 答案的字符串中所做的更改不会影响查询 $$$j$$$ ($$$j > i$$$)。换句话说,对于每个查询,子字符串 $$$s[l \dots r]$$$ 是从最初给定的字符串 $$$s$$$ 中给出的。

正确的括号序列是可以根据以下规则构建的序列:

- 空序列是正确的括号序列;
- 如果“s”是正确的括号序列,则序列“(s)”和“[s]”是正确的括号序列。
- 如果“s”和“t”是正确的括号序列,则序列“st”(序列的串联)是正确的括号序列。

例如序列“”、“(()[])”、“[()()]()”和“(())()”是正确的括号序列,而“(”、“[(])”和“)))”则不是。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

对于每个测试用例,第一行包含一个非空字符串 $$$s$$$,仅包含圆括号 ('(', ')') 和方括号 ('[', ']')。字符串的长度不超过$$$10^6$$$。该字符串至少包含 $$$2$$$ 个字符。

第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来是 $$$q$$$ 行,每行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$ 其中 $$$n$$$ 是 $$$s$$$ 的长度)。保证子串 $$$s[l \dots r]$$$ 的长度为偶数。

保证所有测试用例中给出的所有字符串的长度总和不超过$$$10^6$$$。所有测试用例中给出的所有 $$$q$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,每个查询在单独的行中输出一个整数 $$$x$$$ ($$$x \ge 0$$$) — 使给定子字符串成为正确的括号序列所需的最小成本。

示例

输入 #1

3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2

输出 #1

0
2
1
0
0
0

注意

考虑第一个测试用例。第一个查询描述了整个给定字符串,该字符串可以转换为以下正确的括号序列:“([()])()[[]]”。括号的形式没有改变,所以改变的成本是$$$0$$$。

第二个查询描述子字符串“)[)()]”。可能会变成“(()())”,成本等于$$$2$$$。

第三个查询描述子字符串“))[)”。可能会变成“()()”,成本等于$$$1$$$。

第二个测试用例的子字符串仅包含圆括号。可以证明,任何具有偶数长度的圆括号序列都可以以 $$$0$$$ burles 的成本转换为正确的括号序列。

在第三个测试用例中,单个查询描述的字符串“[]”已经是正确的括号序列。