Changing Brackets

题意翻译

你有一个长度为 $n$ 的括号序列 $s$（下标从 $1$ 到 $n$），序列由小括号和中括号组成。定义该序列中下标从 $x$ 到 $y$ 的连续一段子串为 $s[x\dots y]$。有两种不同的操作： - 花费 $0$ 个单位的代价调换一个括号的方向。具体地，你可以执行如下 $4$ 类操作中的一类： - `(` $\rightarrow$ `)` - `)` $\rightarrow$ `(` - `[` $\rightarrow$ `]` - `]` $\rightarrow$ `[` - 花费 $1$ 个单位的代价将一个中括号替换成一个不同类型相同方向的小括号。具体地，你可以执行如下 $2$ 类操作中的一类： - `[` $\rightarrow$ `(` - `]` $\rightarrow$ `)` 一个合法的括号序列是这么定义的： - 空字符串是一个合法的括号序列。 - 如果 `A` 是一个合法的括号序列，那么 `[A]` 或者 `(A)` 是一个合法的括号序列。 - 如果 `A`、`B` 是一个合法的括号序列，那么 `AB` 是一个合法的括号序列。 现在有 $q$ 次询问，每次询问给定两个整数 $l,r$，求出将 $s[l\dots r]$ 通过若干次操作变成一个合法的括号序列最少需要花费多少单位的代价。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n\leqslant 10^6$，$1\leqslant q\leqslant 2\times 10^5$，$1\leqslant l<r\leqslant n$。 - $\sum n\leqslant 10^6$，$\sum q\leqslant 2\times 10^5$。 Translated by Eason_AC 2021.10.14

题目描述

A sequence of round and square brackets is given. You can change the sequence by performing the following operations: 1. change the direction of a bracket from opening to closing and vice versa without changing the form of the bracket: i.e. you can change '(' to ')' and ')' to '('; you can change '\[' to '\]' and '\]' to '\['. The operation costs $ 0 $ burles. 2. change any square bracket to round bracket having the same direction: i.e. you can change '\[' to '(' but not from '(' to '\['; similarly, you can change '\]' to ')' but not from ')' to '\]'. The operation costs $ 1 $ burle. The operations can be performed in any order any number of times. You are given a string $ s $ of the length $ n $ and $ q $ queries of the type "l r" where $ 1 \le l < r \le n $ . For every substring $ s[l \dots r] $ , find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring $ s[l \dots r] $ has an even length. The queries must be processed independently, i.e. the changes made in the string for the answer to a question $ i $ don't affect the queries $ j $ ( $ j > i $ ). In other words, for every query, the substring $ s[l \dots r] $ is given from the initially given string $ s $ . A correct bracket sequence is a sequence that can be built according the following rules: - an empty sequence is a correct bracket sequence; - if "s" is a correct bracket sequence, the sequences "(s)" and "\[s\]" are correct bracket sequences. - if "s" and "t" are correct bracket sequences, the sequence "st" (the concatenation of the sequences) is a correct bracket sequence. E.g. the sequences "", "(()\[\])", "\[()()\]()" and "(())()" are correct bracket sequences whereas "(", "\[(\])" and ")))" are not.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then $ t $ test cases follow. For each test case, the first line contains a non-empty string $ s $ containing only round ('(', ')') and square ('\[', '\]') brackets. The length of the string doesn't exceed $ 10^6 $ . The string contains at least $ 2 $ characters. The second line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of queries. Then $ q $ lines follow, each of them contains two integers $ l $ and $ r $ ( $ 1 \le l < r \le n $ where $ n $ is the length of $ s $ ). It is guaranteed that the substring $ s[l \dots r] $ has even length. It is guaranteed that the sum of the lengths of all strings given in all test cases doesn't exceed $ 10^6 $ . The sum of all $ q $ given in all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output in a separate line for each query one integer $ x $ ( $ x \ge 0 $ ) — the minimum cost to pay to make the given substring a correct bracket sequence.

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
1
0
0
0

说明

Consider the first test case. The first query describes the whole given string, the string can be turned into the following correct bracket sequence: "(\[()\])()\[\[\]\]". The forms of the brackets aren't changed so the cost of changing is $ 0 $ . The second query describes the substring ")\[)()\]". It may be turned into "(()())", the cost is equal to $ 2 $ . The third query describes the substring "))\[)". It may be turned into "()()", the cost is equal to $ 1 $ . The substrings of the second test case contain only round brackets. It's possible to prove that any sequence of round brackets having an even length may be turned into a correct bracket sequence for the cost of $ 0 $ burles. In the third test case, the single query describes the string "\[\]" that is already a correct bracket sequence.