Advertisement
Josif_tepe

Untitled

May 9th, 2024
704
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e6 + 10;
  4. const int INF = 2e9;
  5. int closing_bracket[maxn];
  6.  
  7. vector<int> segment_tree[3 * maxn];
  8. vector<int> merge_two_nodes(vector<int> & a, vector<int> & b) {
  9.     int i = 0, j = 0;
  10.     vector<int> c;
  11.     while(i < (int) a.size() and j < (int) b.size()) {
  12.         if(a[i] <= b[j]) {
  13.             c.push_back(a[i]);
  14.             i++;
  15.         }
  16.         else {
  17.             c.push_back(b[j]);
  18.             j++;
  19.         }
  20.     }
  21.     while(i < (int) a.size()) {
  22.         c.push_back(a[i]);
  23.         i++;
  24.     }
  25.     while(j < (int) b.size()) {
  26.         c.push_back(b[j]);
  27.         j++;
  28.     }
  29.     return c;
  30. }
  31. void build_tree(int L, int R, int node) {
  32.     if(L == R) {
  33.         segment_tree[node].push_back(closing_bracket[L]);
  34.     }
  35.     else {
  36.         int middle = (L + R) / 2;
  37.         build_tree(L, middle, 2 * node);
  38.         build_tree(middle + 1, R, 2 * node + 1);
  39.         segment_tree[node] = merge_two_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
  40.     }
  41. }
  42. // L R i L R j L R
  43. int query(int L, int R, int node, int i, int j) {
  44.     if(R < i or j < L) {
  45.         return 0;
  46.     }
  47.     if(i <= L and R <= j) {
  48.         return (int) (lower_bound(segment_tree[node].begin(), segment_tree[node].end(), j + 1) - segment_tree[node].begin());
  49.     }
  50.     int middle = (L + R) / 2;
  51.     return query(L, middle, 2 * node, i, j) + query(middle + 1, R, 2 * node + 1, i, j);
  52. }
  53. int main() {
  54.     ios_base::sync_with_stdio(false);
  55.     string s;
  56.     cin >> s;
  57.  
  58.     stack<int> st;
  59.     for(int i = 0; i < (int) s.size(); i++) {
  60.         closing_bracket[i] = INF;
  61.     }
  62.     for(int i = 0; i < (int) s.size(); i++) {
  63.         if(s[i] == '(') {
  64.             st.push(i);
  65.         }
  66.         else {
  67.             if(!st.empty()) {
  68.                 closing_bracket[st.top()] = i;
  69.                 st.pop();
  70.             }
  71.         }
  72.     }
  73.     int n = (int) s.size();
  74.     build_tree(0, n - 1, 1);
  75.  
  76.     int q;
  77.     cin >> q;
  78.     for(int i = 0; i < q; i++) {
  79.         int a, b;
  80.         cin >> a >> b;
  81.  
  82.         a--; b--;
  83.  
  84.         cout << query(0, n - 1, 1, a, b) * 2 << "\n";
  85.     }
  86.    
  87.    
  88.     return 0;
  89. }
  90.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement