fork download
copy 
  1. // author: phucan1402, 3:00 PM 11/10/2025 GMT + 7
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. const int maxn = 1e6;
  6. string s;
  7. struct node{
  8.     int couple;
  9.     int open;
  10.     int close;
  11.     node(int cp = 0, int o = 0, int c = 0) {
  12.         couple = cp;
  13.         open = o;
  14.         close = c;
  15.     }
  16. };
  17. node tree[4 * maxn + 5];
  18. node merge(node l, node r) {
  19.     node res;
  20.     int new_cp = min(l.open, r.close);
  21.     res.couple = l.couple + r.couple + new_cp * 2;
  22.     res.open = l.open + r.open - new_cp;
  23.     res.close = l.close + r.close - new_cp;
  24.     return res;
  25. }
  26. void build(int id, int l, int r) {
  27.     if(l == r) {
  28.         if(s[l] == '(') {
  29.             tree[id] = node(0,1,0);
  30.         }
  31.         else tree[id] = node(0,0,1);
  32.         return;
  33.     }
  34.     int m = (l + r)/2;
  35.     build(2 * id, l, m);
  36.     build(2 * id + 1, m + 1, r);
  37.     tree[id] = merge(tree[id*2], tree[id*2+1]);
  38. }
  39. void update(int id, int l,int r, int pos) {
  40.     if(l == r) {
  41.         if(s[l] == '(') {
  42.             s[l] = ')';
  43.             tree[id] = node(0,0,1);
  44.         }
  45.         else {
  46.             s[l] = '(';
  47.             tree[id] = node(0,1,0);
  48.         }
  49.         return;
  50.     }
  51.     int m = (l + r)/2;
  52.     if(pos <= m) update(2*id,l,m,pos);
  53.     else update(2*id+1,m+1,r,pos);
  54.     tree[id] = merge(tree[2 * id], tree[2 * id + 1]);
  55. }
  56. node query(int id, int l, int r, int u, int v) {
  57.     if(l > v || r < u) return node();
  58.     if(u <= l && r <= v) return tree[id];
  59.     int m = (l + r)/2;
  60.     return merge(query(2*id,l,m,u,v), query(2*id+1,m+1,r,u,v));
  61. }
  62. int main() {
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     int n,m; cin >> n >> m;
  66.     cin >> s;
  67.     build(1,0,n-1);
  68.     while(m--) {
  69.         int type; cin >> type;
  70.         if(type == 1) {
  71.             int u,v; cin >> u >> v;
  72.             node ans = query(1,0,n-1,u-1,v-1);
  73.             if(ans.open == 0 && ans.close == 0) cout << 1;
  74.             else cout << 0;
  75.         }
  76.         else {
  77.             int u; cin >> u;
  78.             update(1,0,n-1,u-1);
  79.         }
  80.     }
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 50556KB
comments (?)
stdin
copy 
8 7
()))(())
1 1 2
1 3 4
0 3
1 1 4
1 5 8
0 6
1 5 8
stdout
copy 
10110
https://ideone.com/bdWsMQ
language:
C++ (gcc 8.3)
created:
2 days 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!