考虑到括号变方向并不需要花费,所以并不用考虑左右括号,考虑小中括号就行了。
因为一个合法括号序列长度为偶数,则说明对于一对括号其左右括号位置奇偶肯定相反。
所以一个类型的括号在奇数位和在偶数位的数量之差就为需要改变类型的括号的数量。
这部分用前缀和维护即可。
时间复杂度 \(O(\sum n + \sum q)\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: G. Changing Brackets
// Contest: Codeforces - Codeforces Round 748 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1593/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 N = 1e6 + 10;
char s[N];
int h[N];
int main() {
function<void ()> solve = []() -> void {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1];
if (s[i] == '[' || s[i] == ']') {
h[i] += (i & 1 ? 1 : -1);
}
}
int q;
scanf("%d", &q);
for (; q; q--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", abs(h[r] - h[l - 1]));
}
};
int _;
scanf("%d", &_);
for (int i = 1; i <= _; i++) {
solve();
}
return 0;
}