CCCPaste

Untitled

#include 
#include 
#include 
//#include 
using namespace std;
const int maxn = 1e6 + 10;
vector segment_tree[3 * maxn];
int next_idx[maxn];
void build(int L, int R, int position) {
    if(L == R) {
        segment_tree[position].push_back(next_idx[L]);
    }
    else {
        int middle = (L + R) / 2;
        build(L, middle, 2 * position);
        build(middle + 1, R, 2 * position + 1);
        merge(segment_tree[2 * position].begin(), segment_tree[2 * position].end(), segment_tree[2 * position + 1].begin(), segment_tree[2 * position + 1].end(), back_inserter(segment_tree[position]));
    }
}
int query(int L, int R, int position, int i, int j, int x) {
    // L  R i L R j L R
    if(i <= L and R <= j) {
        return lower_bound(segment_tree[position].begin(), segment_tree[position].end(), x) - segment_tree[position].begin();
    }
    if(R < i or j < L) {
        return 0;
    }
    int middle = (L + R) / 2;
    return query(L, middle, 2 * position, i, j, x) + query(middle + 1, R, 2 * position + 1, i, j, x);
}
int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    stack st;
    for(int i = 0; i < s.size(); i++) {
        next_idx[i] = (int) s.size();
    }
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '(') {
            st.push(i);
        }
        else {
            if(!st.empty()) {
                next_idx[st.top()] = i;
                st.pop();
            }
        }
    }
    int q;
    cin >> q;
    build(0, s.size(), 1);
    for(int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        cout << query(0, s.size(), 1, a, b, b + 1) * 2 << "\n";
        
    }
    return 0;
}
/*
 ())(())(())(
 1NN65NN109NNN
 
 
 */