Changing Brackets
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 2200
Tags: constructive algorithms, data structures, dp, greedy

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2

Example output:
0
2
1
0
0
0

Editorial:
Consider a substring $$$t = s[l \dots r]$$$. Let's call square brackets located in odd positions in the substring odd brackets, and square brackets located in even positions even brackets. Let $$$cnt_{odd}$$$ be the number of odd brackets, $$$cnt_{even}$$$ be the number of even brackets, $$$cnt_{all} = cnt_{odd} + cnt_{even}$$$ be the number of all square brackets. Let's prove that the string $$$t$$$ can be turned into a correct bracket sequence for $$$0$$$ burles if and only if $$$cnt_{odd} = cnt_{even}$$$.
Let's prove the necessary condition. Suppose the initial substring has been turned into a correct bracket sequence. Since we have paid $$$0$$$ burles, there's no bracket which form has been changed. Therefore, $$$cnt_{odd}$$$ for the new sequence is the same as $$$cnt_{odd}$$$ for the initial sequence, the similar situation happens with $$$cnt_{even}$$$.
Let's say that two square brackets form a pair if the left one is an opening bracket and the right one is a closing bracket and the substring between them is a correct bracket sequence. A pair can be formed only by one odd bracket and one even bracket because between them is placed an even number of brackets (since it's a correct bracket sequence) so the difference between their indices is odd. In a correct bracket sequence, each square bracket has a pairwise bracket. Therefore, a correct bracket sequence contains $$$\frac{cnt_{all}}{2}$$$ pairs of brackets so $$$cnt_{odd} = cnt_{even} = \frac{cnt_{all}}{2}$$$.
Let's prove the sufficient condition. Suppose the initial substring contains equal numbers of odd and even brackets. Let's prove by induction that the substring may be turned into a correct bracket sequence for $$$0$$$ burles.
Suppose $$$cnt_{odd} = cnt_{even} = 0$$$. So the initial substring contains only round brackets. Let's make the first $$$\frac{r - l + 1}{2}$$$ brackets opening and the other brackets closing. The resulting sequence is a correct bracket sequence whereas we haven't changed the form of any bracket so the cost is equal to $$$0$$$.
A correct bracket sequence has two important properties:
• after deleting its substring being a correct bracket sequence, the resulting string is a correct bracket sequence;
• after inserting at any place any correct bracket sequence, the resulting string is a correct bracket sequence.
These properties can be applied to an incorrect bracket sequence, too: after deleting a substring being a correct bracket subsequence from an incorrect bracket sequence or inserting a correct bracket sequence into an incorrect one, the resulting sequence is an incorrect bracket sequence.
Consider a substring $$$t$$$ such that $$$cnt_{odd} = cnt_{even} > 0$$$. Suppose we have proved before that each substring $$$t$$$ having $$$cnt_{odd} = cnt_{even}$$$ decreased by $$$1$$$ can be turned into a correct bracket sequence for $$$0$$$ burles. Let's find two square brackets such that one of them is odd and another one is even and there are no square brackets between them. There's an even number of round brackets between them that can be turned into a correct bracket sequence for $$$0$$$ burles. Let's make the left found bracket opening and the right one closing. Then the substring starting at the left found bracket and ending at the right found bracket is a correct bracket sequence. Let's remove it from $$$t$$$. The resulting string contains $$$cnt_{odd} - 1$$$ odd brackets and $$$cnt_{even} - 1$$$ even brackets so, by the assumption of induction, it can be turned into a correct bracket sequence for $$$0$$$ burles. Let's do it and then insert the removed string into its place. Since we insert a correct bracket sequence into a correct bracket sequence, the resulting string is a correct bracket sequence.
Actually, the operations of inserting and removing are not allowed, they have been used for clarity, the string can be turned into a correct bracket sequence without these operations as follows: let's turn the substring we have removed into a correct bracket sequence (as it was described above), then change the other brackets of the string the same way as it was done with the string that was the result after removing. The resulting string is a correct bracket sequence. Therefore, the illegal operations of inserting and removing are not necessary, all other operations cost $$$0$$$ burles so the substring $$$t$$$ can be turned into a correct bracket sequence for $$$0$$$ burles.
Therefore, to turn a substring into a correct bracket sequence, we need to get a sequence such that $$$cnt_{odd} = cnt_{even}$$$. Suppose, initiallly, $$$cnt_{odd} > cnt_{even}$$$. Let's pay $$$cnt_{odd} - cnt_{even}$$$ burles to replace $$$cnt_{odd} - cnt_{even}$$$ odd brackets with round brackets. If $$$cnt_{odd} < cnt_{even}$$$, let's replace $$$cnt_{even} - cnt_{odd}$$$ even brackets with round brackets. Anyway, we must pay $$$|cnt_{odd} - cnt_{even}|$$$ burles. We cannot pay less than this value because for a correct bracket sequence, $$$cnt_{odd} = cnt_{even}$$$. But there's no need to pay more than this value, because, if we turn the initial substring into a sequence with $$$cnt_{odd} = cnt_{even}$$$, we can turn it into a correct bracket sequence for free. Therfore, the answer for a given question is $$$|cnt_{odd} - cnt_{even}|$$$.
Since we must answer the queries fast, let's use a concept of prefix sums. If the given string $$$s$$$ contains $$$n$$$ brackets, let's create arrays $$$psumOdd$$$ and $$$psumEven$$$ with the length $$$n + 1$$$. $$$psumOdd[i]$$$ will contain the number of odd brackets on the prefix of the string $$$s$$$ with the length $$$i$$$, $$$psumEven[i]$$$ — the same value for even brackets. Let's initialize $$$psumOdd[0] = psumEven[0] = 0$$$ and then iterate $$$i$$$ from $$$1$$$ to $$$n$$$. Let's initialize $$$psumOdd[i] = psumOdd[i - 1]$$$ and $$$psumEven[i] = psumEven[i - 1]$$$. If the $$$i$$$-th bracket is round, then the current values are correct. Otherwise, let's find out what bracket is it. If $$$i$$$ is odd, the bracket is odd so we must increase $$$psumOdd[i]$$$ by $$$1$$$. If $$$i$$$ is even, the bracket is even so we must increase $$$psumEven[i]$$$ by $$$1$$$.
To get the answer for a current $$$l$$$ and $$$r$$$, let's calculate $$$cnt_{odd}$$$ and $$$cnt_{even}$$$. $$$cnt_{odd}$$$ is a number of odd brackets that belong to the prefix with the length $$$r$$$ but not to the prefix with the length $$$l - 1$$$ so $$$cnt_{odd} = psumOdd[r] - psumOdd[l - 1]$$$. Similarly, $$$cnt_{even} = psumEven[r] - psumEven[l - 1]$$$. The remaining thing is to output $$$|cnt_{odd} - cnt_{even}|$$$.