离线算法 + 树状数组

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5, maxm = 1e5 + 5;

struct Query {
    int id, l, r;

    bool operator < (const Query &b) const {
        return r < b.r;
    }
} q[maxm];

int n, m, ans[maxm], mat[maxn]; // 如果 s[i]==')' mat[i] 对应 s[i] 匹配的 '(' 的下标
char s[maxn];

// 树状数组
int bit[maxn];
int lowbit(int x) { return x & -x; }
void add(int p) {
    for (int i = p; i <= n; i += lowbit(i))
        bit[i]++;
}
int query(int p) {
    int res = 0;
    for (int i = p; i; i -= lowbit(i))
        res += bit[i];
    return res;
}
int query(int l, int r) {
    return query(r) - query(l-1);
}

void init() {
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(')
            stk.push(i);
        else if (!stk.empty()) {
            mat[i] = stk.top();
            stk.pop();
        }
    }
}

int main() {
    scanf("%s%d", s+1, &m);
    n = strlen(s+1);
    init();
    for (int i = 1; i <= m; i++) {
        q[i].id = i;
        scanf("%d%d", &q[i].l, &q[i].r);
    }
    sort(q+1, q+m+1);
    for (int i = 1, r = 1; i <= m && r <= n; r++) {
        // [1, r] 的 ')' 匹配的 '('（如果有的话）对应的位置标记为1
        if (s[r] == ')' && mat[r])
            add(mat[r]);
        while (i <= m && q[i].r == r) {
            ans[q[i].id] = query(q[i].l, q[i].r) * 2;
            i++;
        }
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}