fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 500005;
  5.  
  6. int sum[4 * MAXN], minPref[4 * MAXN], maxPref[4 * MAXN];
  7. int assign_tag[4 * MAXN];   // 2 = no assignment, 1 = '(', -1 = ')'
  8. bool flip_tag[4 * MAXN];
  9.  
  10. inline void applyAssign(int node, int val, int len) {
  11.     assign_tag[node] = val;
  12.     flip_tag[node] = false;
  13.     sum[node] = val * len;
  14.     if (val == 1) {
  15.         minPref[node] = 0;
  16.         maxPref[node] = len;
  17.     } else {
  18.         minPref[node] = -len;
  19.         maxPref[node] = 0;
  20.     }
  21. }
  22.  
  23. inline void applyFlip(int node, int len) {
  24.     if (assign_tag[node] != 2) {
  25.         applyAssign(node, -assign_tag[node], len);
  26.     } else {
  27.         sum[node] = -sum[node];
  28.         int tmp = minPref[node];
  29.         minPref[node] = -maxPref[node];
  30.         maxPref[node] = -tmp;
  31.         flip_tag[node] ^= 1;
  32.     }
  33. }
  34.  
  35. inline void push(int node, int l, int r) {
  36.     int mid = (l + r) / 2;
  37.     int left = node * 2, right = node * 2 + 1;
  38.     if (assign_tag[node] != 2) {
  39.         applyAssign(left, assign_tag[node], mid - l + 1);
  40.         applyAssign(right, assign_tag[node], r - mid);
  41.         assign_tag[node] = 2;
  42.     }
  43.     if (flip_tag[node]) {
  44.         applyFlip(left, mid - l + 1);
  45.         applyFlip(right, r - mid);
  46.         flip_tag[node] = false;
  47.     }
  48. }
  49.  
  50. inline void pull(int node) {
  51.     int left = node * 2, right = node * 2 + 1;
  52.     sum[node] = sum[left] + sum[right];
  53.     minPref[node] = min(minPref[left], sum[left] + minPref[right]);
  54.     maxPref[node] = max(maxPref[left], sum[left] + maxPref[right]);
  55. }
  56.  
  57. void build(int node, int l, int r, const vector<int>& a) {
  58.     assign_tag[node] = 2;
  59.     flip_tag[node] = false;
  60.     if (l == r) {
  61.         int val = a[l - 1];
  62.         sum[node] = val;
  63.         minPref[node] = min(0, val);
  64.         maxPref[node] = max(0, val);
  65.         return;
  66.     }
  67.     int mid = (l + r) / 2;
  68.     build(node * 2, l, mid, a);
  69.     build(node * 2 + 1, mid + 1, r, a);
  70.     pull(node);
  71. }
  72.  
  73. void updateAssign(int node, int l, int r, int ql, int qr, int val) {
  74.     if (ql <= l && r <= qr) {
  75.         applyAssign(node, val, r - l + 1);
  76.         return;
  77.     }
  78.     push(node, l, r);
  79.     int mid = (l + r) / 2;
  80.     if (ql <= mid) updateAssign(node * 2, l, mid, ql, qr, val);
  81.     if (qr > mid) updateAssign(node * 2 + 1, mid + 1, r, ql, qr, val);
  82.     pull(node);
  83. }
  84.  
  85. void updateFlip(int node, int l, int r, int ql, int qr) {
  86.     if (ql <= l && r <= qr) {
  87.         applyFlip(node, r - l + 1);
  88.         return;
  89.     }
  90.     push(node, l, r);
  91.     int mid = (l + r) / 2;
  92.     if (ql <= mid) updateFlip(node * 2, l, mid, ql, qr);
  93.     if (qr > mid) updateFlip(node * 2 + 1, mid + 1, r, ql, qr);
  94.     pull(node);
  95. }
  96.  
  97. struct Node {
  98.     int sum, minPref, maxPref;
  99. };
  100.  
  101. Node query(int node, int l, int r, int ql, int qr) {
  102.     if (ql <= l && r <= qr) {
  103.         return {sum[node], minPref[node], maxPref[node]};
  104.     }
  105.     push(node, l, r);
  106.     int mid = (l + r) / 2;
  107.  
  108.     if (qr <= mid) return query(node * 2, l, mid, ql, qr);
  109.     if (ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);
  110.  
  111.     Node left = query(node * 2, l, mid, ql, qr);
  112.     Node right = query(node * 2 + 1, mid + 1, r, ql, qr);
  113.     Node res;
  114.     res.sum = left.sum + right.sum;
  115.     res.minPref = min(left.minPref, left.sum + right.minPref);
  116.     res.maxPref = max(left.maxPref, left.sum + right.maxPref);
  117.     return res;
  118. }
  119.  
  120. int main() {
  121.     ios::sync_with_stdio(false);
  122.     cin.tie(nullptr);
  123.  
  124.     int n, Q;
  125.     if (!(cin >> n >> Q)) return 0;
  126.     string S;
  127.     cin >> S;
  128.     vector<int> a(n);
  129.     for (int i = 0; i < n; ++i) {
  130.         a[i] = (S[i] == '(') ? 1 : -1;
  131.     }
  132.     build(1, 1, n, a);
  133.  
  134.     while (Q--) {
  135.         int L, H;
  136.         char c;
  137.         cin >> L >> H >> c;
  138.  
  139.         // Cực kỳ quan trọng để tránh Segment Tree bị lặp vô hạn
  140.         if (L > H) swap(L, H); 
  141.  
  142.         if (c == '?') {
  143.             Node res = query(1, 1, n, L, H);
  144.             if (res.sum == 0 && res.minPref >= 0)
  145.                 cout << "yes\n";
  146.             else
  147.                 cout << "no\n";
  148.         } else if (c == '(') {
  149.             updateAssign(1, 1, n, L, H, 1);
  150.         } else if (c == ')') {
  151.             updateAssign(1, 1, n, L, H, -1);
  152.         } else if (c == '-') {
  153.             updateFlip(1, 1, n, L, H);
  154.         }
  155.     }
  156.     return 0;
  157. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ldDwvo
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!