CCCPaste

Untitled

#include 
using namespace std;
const int maxn = 1e6 + 10;
const int INF = 2e9;
int closing_bracket[maxn];

vector segment_tree[3 * maxn];
vector merge_two_nodes(vector & a, vector & b) {
    int i = 0, j = 0;
    vector c;
    while(i < (int) a.size() and j < (int) b.size()) {
        if(a[i] <= b[j]) {
            c.push_back(a[i]);
            i++;
        }
        else {
            c.push_back(b[j]);
            j++;
        }
    }
    while(i < (int) a.size()) {
        c.push_back(a[i]);
        i++;
    }
    while(j < (int) b.size()) {
        c.push_back(b[j]);
        j++;
    }
    return c;
}
void build_tree(int L, int R, int node) {
    if(L == R) {
        segment_tree[node].push_back(closing_bracket[L]);
    }
    else {
        int middle = (L + R) / 2;
        build_tree(L, middle, 2 * node);
        build_tree(middle + 1, R, 2 * node + 1);
        segment_tree[node] = merge_two_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
    }
}
// L R i L R j L R 
int query(int L, int R, int node, int i, int j) {
    if(R < i or j < L) {
        return 0;
    }
    if(i <= L and R <= j) {
        return (int) (lower_bound(segment_tree[node].begin(), segment_tree[node].end(), j + 1) - segment_tree[node].begin());
    }
    int middle = (L + R) / 2;
    return query(L, middle, 2 * node, i, j) + query(middle + 1, R, 2 * node + 1, i, j);
}
int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;

    stack st;
    for(int i = 0; i < (int) s.size(); i++) {
        closing_bracket[i] = INF;
    }
    for(int i = 0; i < (int) s.size(); i++) {
        if(s[i] == '(') {
            st.push(i);
        }
        else {
            if(!st.empty()) {
                closing_bracket[st.top()] = i;
                st.pop();
            }
        }
    }
    int n = (int) s.size();
    build_tree(0, n - 1, 1);

    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;

        a--; b--;

        cout << query(0, n - 1, 1, a, b) * 2 << "\n";
    }
    
    
    return 0;
}