k.cpp

#include <bits/stdc++.h>
#define s second
#define f first
#define lb lower_bound
#define pb push_back
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mod1 = 1e9 + 7;
const int mod2 = 676767677;
const int MAXN = 1e6 + 5;
const int INF = 1e9 + 7;

string s;

pair <int, pair <int, int> > t[4 * MAXN];

pair <int, pair <int, int> > combine(pair <int, pair <int, int> > left, pair <int, pair <int, int> > right){
    pair <int, pair <int, int> > tmp;

    tmp.f = left.f + right.f;
    int k = min(left.s.f, right.s.s);
    tmp.f += k;
    tmp.s.f = left.s.f + right.s.f - k;
    tmp.s.s = left.s.s + right.s.s - k;
    return tmp;
}

void build(int v, int tl, int tr){
    if (tl > tr){
        return;
    }
    if (tl == tr){
        t[v] = {0, {0, 0}};
        if (s[tl] == '('){
            t[v].s.f = 1;
        }
        else{
            t[v].s.s = 1;
        }
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build((v << 1) | 1, tm + 1, tr);
    t[v] = combine(t[v << 1], t[(v << 1) | 1]);
}

pair <int, pair <int, int> > get(int v, int tl, int tr, int l, int r){

    if (l > r){
        return {0, {0, 0}};
    }
    if (tl == l && tr == r){
        return t[v];
    }
    int tm = (tl + tr) >> 1;

    return combine(get(v << 1, tl, tm, l, min(r, tm)),
                   get((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r));
}


void solve_problem() {

    cin >> s;
    int n = s.size();
    s = "#" + s;

    build(1, 1, n);
    int q;
    cin >> q;

    for (int i = 1; i <= q; i++){

        int l, r;
        cin >> l >> r;

        cout << get(1, 1, n, l, r).first * 2 << "\n";
    }

    return;
}

signed main () {
    IOS

    //freopen("sum.in", "r", stdin);
    //freopen("sum.out", "w", stdout);

    int tt = 1;
    //cin >> tt;

    while (tt--) {
      solve_problem();
    }
}