Advertisement
YEZAELP

C. Sereja and Brackets

Feb 1st, 2021
193
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None
  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.  
Advertisement
RAW Paste Data Copied
Advertisement