fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair <int, int> ii;
  7.  
  8. const ll LINF = 1e18;
  9. const int INF = 1e9;
  10.  
  11. const int N = 1e6 + 5;
  12.  
  13. int n, m;
  14. string s;
  15.  
  16. struct Node {
  17. int matched = 0, open_rem = 0, close_rem = 0;
  18.  
  19. Node() {}
  20.  
  21. Node(char c) {
  22. if (c == '(') open_rem = 1;
  23. if (c == ')') close_rem = 1;
  24. }
  25.  
  26. Node operator+(const Node& other) const {
  27. Node res;
  28. int bonus = min(open_rem, other.close_rem); // số cặp ngoặc đúng có thêm
  29. res.matched = matched + other.matched + bonus; // số cặp ngoặc đúng sau khi gộp
  30. res.open_rem = (open_rem - bonus) + other.open_rem; // số ngoặc mở còn thừa sau khi gộp
  31. res.close_rem = close_rem + (other.close_rem - bonus); // số ngoặc đóng còn thừa sau khi gộp
  32. return res;
  33. }
  34. };
  35.  
  36. Node seg[4 * N];
  37.  
  38. void build(int id, int l, int r) {
  39. if (l == r) {
  40. seg[id] = Node(s[l]);
  41. return;
  42. }
  43. int mid = (l + r) >> 1;
  44. build(id * 2, l, mid);
  45. build(id * 2 + 1, mid + 1, r);
  46. seg[id] = seg[id * 2] + seg[id * 2 + 1];
  47. }
  48.  
  49. Node get(int id, int l, int r, int u, int v) {
  50. if (l > v || r < u) return Node();
  51. if (u <= l && r <= v) return seg[id];
  52. int mid = (l + r) >> 1;
  53. return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  54. }
  55.  
  56. int main() {
  57. ios::sync_with_stdio(false);
  58. cin.tie(nullptr);
  59. cin >> s >> m;
  60. n = s.size();
  61.  
  62. build(1, 0, n - 1);
  63.  
  64. for (int i = 0; i < m; i++) {
  65. int l, r;
  66. cin >> l >> r;
  67. l--, r--;
  68. cout << get(1, 0, n - 1, l, r).matched * 2 << '\n';
  69. }
  70. }
Success #stdin #stdout 0.01s 50440KB
stdin
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
stdout
0
0
2
10
4
6
6