题意
给出一个圆括号和方括号组成的括号序列，可以执行以下操作任意次
1.改变某个括号的方向 花费为0
2.把某个方括号改成圆括号 花费为1
q次询问，每次询问l,r，问让子串([l,r])成为合法括号序列的最小开销，保证子串长度为偶数。
每次询问是独立的
(tle 100)组数据，(2le n le sum n = sum s.length() <= 1e6, sum q le 2e5)
sol
考虑找出哪些方括号不用改为圆括号
若一对方括号之间没有夹杂着不合法的括号序列（通过若干次操作1不能变合法的序列），那么这对方括号就不用改成圆括号
而长为偶数的括号序列一定合法，因此一对不用改成圆括号的方括号，一定是在奇偶性相反的位置上。
如果位于奇数位置上的方括号有a个，偶数位置上的方括号有b个，那么让奇数位置和偶数位置按顺序一一配对，剩下的方括号改成圆括号，就能得到合法括号序列。
这是由于配对的方括号之间可以变成合法括号序列，将以每对配对的方括号为端点的子串从序列中删去，剩余位置的奇偶性将会发生变化（合法括号序列长度为偶数）。而由于总长度也为偶数，因此剩下的序列中的方括号全部改为圆括号后也可以通过操作1变为合法括号序列。
剩下的括号序列中，方括号要么全在奇数位置，要么全在偶数位置。这些方括号之间是无法配对的，因此它们一定得改成圆括号。
于是，对于一个区间 求出奇数位置和偶数位置上各有多少个方括号 前缀和(O(1))求一下绝对值的差即可
// Problem: G. Changing Brackets
// Contest: Codeforces - Codeforces Round #748 (Div. 3)
// URL: https://codeforces.com/contest/1593/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
#define ll long long
int n, m, k, tot;
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
return s * f;
}
int podd[maxn], peven[maxn];
char s[maxn];
int main() {
int T = rd();
while (T--) {
scanf("%s", s + 1);
n = strlen(s+1);
for (int i = 1; i <= n; i++) {
if ((i&1) && (s[i] == '[' || s[i] == ']')) {
podd[i] = 1;
} else podd[i] = 0;
if ((i&1)==0 && (s[i] == '[' || s[i] == ']')) {
peven[i] = 1;
} else peven[i] = 0;
podd[i] += podd[i-1];
peven[i] += peven[i-1];
}
int q = rd();
while (q--) {
int l = rd(), r = rd();
int cnto = podd[r] - podd[l-1];
int cnte = peven[r] - peven[l-1];
printf("%d
", abs(cnto - cnte));
}
}
return 0;
}