# C. Sereja and Brackets

Feb 1st, 2021
193
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. using pi = pair <int, int>;
6. using pii = pair <int, pi>;
7. int tree[2*(1 << 21)];
8. int L[2 * (1 << 21)];
9. int R[2 * (1 << 21)];
10. int n;
11. string str;
12.
13. void build(int idx, int l, int r){
14.     if(l == r){
15.         if(str[l-1] == '(') L[idx] = 1;
16.         else R[idx] = 1;
17.         return ;
18.     }
19.
20.     int mid = (l + r)/ 2;
21.     build(2*idx, l, mid);
22.     build(2*idx + 1, mid+1, r);
23.     L[idx] = L[2*idx];
24.     R[idx] = R[2*idx + 1];
25.
26.     int brackets = min(L[idx], R[idx]);
27.     tree[idx] = tree[2*idx] + tree[2*idx + 1] + 2*brackets;
28.     L[idx] = L[idx] - brackets + L[2*idx + 1];
29.     R[idx] = R[idx] - brackets + R[2*idx];
30. }
31.
32. pii query(int idx, int l, int r, int s, int e){ // l, r = now // s, e = find
33.     if(l > e or r < s)
34.         return {0, {0, 0}};
35.     if(s <= l and r <= e)
36.         return {tree[idx], {L[idx], R[idx]}};
37.
38.     int mid = (l + r)/ 2;
39.     pii QL = query(2*idx, l, mid, s, e);
40.     pii QR = query(2*idx + 1, mid + 1, r, s, e);
41.     int ql_tree = QL.first;
42.     int qr_tree = QR.first;
43.     int ql_L = QL.second.first;
44.     int qr_L = QR.second.first;
45.     int ql_R = QL.second.second;
46.     int qr_R = QR.second.second;
47.
48.     int brackets = min(ql_L, qr_R);
49.     return { ql_tree + qr_tree + (2*brackets)
50.         ,{ ql_L - brackets + qr_L
51.         ,  qr_R - brackets + ql_R }};
52. }
53.
54. int main(){
55.
56.     cin >> str;
57.     n = str.size();
58.
59.     build(1, 1, n);
60.
61.     int q;
62.     scanf("%d", &q);
63.     while(q--){
64.         int l, r;
65.         scanf("%d%d",&l, &r);
66.         printf("%d\n", query(1, 1, n, l, r));
67.     }
68.
69.     return 0;
70. }
71.