C. Sereja and Brackets

#include <bits/stdc++.h>

using namespace std;

using pi = pair <int, int>;
using pii = pair <int, pi>;
int tree[2*(1 << 21)];
int L[2 * (1 << 21)];
int R[2 * (1 << 21)];
int n;
string str;

void build(int idx, int l, int r){
    if(l == r){
        if(str[l-1] == '(') L[idx] = 1;
        else R[idx] = 1;
        return ;
    }

    int mid = (l + r)/ 2;
    build(2*idx, l, mid);
    build(2*idx + 1, mid+1, r);
    L[idx] = L[2*idx];
    R[idx] = R[2*idx + 1];

    int brackets = min(L[idx], R[idx]);
    tree[idx] = tree[2*idx] + tree[2*idx + 1] + 2*brackets;
    L[idx] = L[idx] - brackets + L[2*idx + 1];
    R[idx] = R[idx] - brackets + R[2*idx];
}

pii query(int idx, int l, int r, int s, int e){ // l, r = now // s, e = find
    if(l > e or r < s)
        return {0, {0, 0}};
    if(s <= l and r <= e)
        return {tree[idx], {L[idx], R[idx]}};

    int mid = (l + r)/ 2;
    pii QL = query(2*idx, l, mid, s, e);
    pii QR = query(2*idx + 1, mid + 1, r, s, e);
    int ql_tree = QL.first;
    int qr_tree = QR.first;
    int ql_L = QL.second.first;
    int qr_L = QR.second.first;
    int ql_R = QL.second.second;
    int qr_R = QR.second.second;

    int brackets = min(ql_L, qr_R);
    return { ql_tree + qr_tree + (2*brackets)
        ,{ ql_L - brackets + qr_L
        ,  qr_R - brackets + ql_R }};
}

int main(){

    cin >> str;
    n = str.size();

    build(1, 1, n);

    int q;
    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d%d",&l, &r);
        printf("%d\n", query(1, 1, n, l, r));
    }

    return 0;
}