CF1593G Changing Brackets

给定一个由圆括号和方括号组成的序列。你可以通过以下操作改变该序列： 1. 改变括号的方向，即将左括号变为右括号，右括号变为左括号，但不改变括号的类型：即可以将 '(' 变为 ')'，')' 变为 '('；可以将 '\[' 变为 '\]'，'\]' 变为 '\['。该操作费用为 $0$ 布尔。 2. 将任意方括号变为相同方向的圆括号：即可以将 '\[' 变为 '('，但不能将 '(' 变为 '\['；同理，可以将 '\]' 变为 ')'，但不能将 ')' 变为 '\]'。该操作费用为 $1$ 布尔。 上述操作可以以任意顺序、任意次数进行。 给定一个长度为 $n$ 的字符串 $s$，以及 $q$ 个查询，每个查询为 "l r"，其中 $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 \times 10^5$），表示查询的数量。 接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l < r \le n$，其中 $n$ 是 $s$ 的长度）。保证子串 $s[l \dots r]$ 的长度为偶数。 保证所有测试用例中所有字符串的总长度不超过 $10^6$。所有测试用例中所有 $q$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例的每个查询，输出一个整数 $x$（$x \ge 0$），表示将给定子串变为合法括号序列所需支付的最小费用。每个查询输出一行。

考虑第一个测试用例。第一个查询描述了整个给定字符串，可以将其变为如下合法括号序列："(\[()\])()\[\[\]\]"。括号的类型未发生变化，因此费用为 $0$。 第二个查询描述的子串为 ")\[)()\]"。可以将其变为 "(()())"，费用为 $2$。 第三个查询描述的子串为 "))\[)"。可以将其变为 "()()"，费用为 $1$。 第二个测试用例的所有子串仅包含圆括号。可以证明，任何长度为偶数的圆括号序列都可以以 $0$ 费用变为合法括号序列。 第三个测试用例的唯一查询描述的字符串为 "\[\]"，它本身就是合法括号序列。 由 ChatGPT 4.1 翻译