fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8.  
  9. #pragma GCC optimize("Ofast")
  10. #pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
  11. #pragma GCC optimize("unroll-loops")
  12.  
  13. typedef long long int ll;
  14. typedef long double ld;
  15.  
  16. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
  17. #define endl '\n'
  18. #define pb push_back
  19. #define conts continue
  20. #define all(a) a.begin(),a.end()
  21. #define rall(a) a.rbegin(), a.rend()
  22. #define yes cout << "Yes" << endl
  23. #define no cout << "No" << endl
  24. #define ff first
  25. #define ss second
  26. #define ceil2(x,y) (x+y-1) / y
  27. #define sz(a) a.size()
  28. #define setbits(x) __builtin_popcountll(x)
  29. #ifndef ONLINE_JUDGE
  30. #define debug(x) cout << #x <<" = "; print(x); cout << endl;
  31. #else
  32. #define debug(x)
  33. #endif
  34.  
  35. bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}
  36.  
  37. void print(ll t) {cout << t;}
  38. void print(int t) {cout << t;}
  39. void print(string t) {cout << t;}
  40. void print(char t) {cout << t;}
  41. void print(double t) {cout << t;}
  42. void print(ld t) {cout << t;}
  43.  
  44. template <class T, class V> void print(pair <T, V> p);
  45. template <class T> void print(vector <T> v);
  46. template <class T> void print(set <T> v);
  47. template <class T, class V> void print(map <T, V> v);
  48. template <class T> void print(multiset <T> v);
  49. template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
  50. template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  51. template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  52. template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  53. template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
  54.  
  55. const ll MOD = 1e9 + 7;
  56. const ll maxn = 1e5 + 5;
  57. const ll inf = 1e18;
  58.  
  59. struct segtree {
  60.     /*=======================================================*/
  61.  
  62.     struct stnode {
  63.         ll minpref, sum;
  64.     };
  65.  
  66.     ll siz = 1;
  67.     vector<stnode> arr;
  68.  
  69.     stnode NEUTRAL_STNODE = {0,0};
  70.  
  71.     void merge(stnode &curr, stnode &left, stnode &right) {
  72.         curr.minpref = min(left.minpref, left.sum + right.minpref);
  73.         curr.sum = left.sum + right.sum;
  74.     }
  75.  
  76.     stnode convert(ll n) {
  77.         return {n,n};
  78.     }
  79.  
  80.     /*=======================================================*/
  81.  
  82.     void init(ll n) {
  83.         while (siz < n) {
  84.             siz *= 2;
  85.         }
  86.  
  87.         arr.assign(2 * siz, NEUTRAL_STNODE);
  88.     }
  89.  
  90.     void build(vector<ll> &a, ll n, ll x, ll lx, ll rx) {
  91.         if (rx - lx == 1) {
  92.             if (lx < n) {
  93.                 arr[x] = convert(a[lx]);
  94.             }
  95.  
  96.             return;
  97.         }
  98.  
  99.         ll mid = (lx + rx) / 2;
  100.  
  101.         build(a, n, 2 * x + 1, lx, mid);
  102.         build(a, n, 2 * x + 2, mid, rx);
  103.  
  104.         merge(arr[x], arr[2 * x + 1], arr[2 * x + 2]);
  105.     }
  106.  
  107.     void pupd(ll i, ll v, ll x, ll lx, ll rx) {
  108.         if (rx - lx == 1) {
  109.             arr[x] = convert(v);
  110.             return;
  111.         }
  112.  
  113.         ll mid = (lx + rx) / 2;
  114.  
  115.         if (i < mid) {
  116.             pupd(i, v, 2 * x + 1, lx, mid);
  117.         }
  118.         else {
  119.             pupd(i, v, 2 * x + 2, mid, rx);
  120.         }
  121.  
  122.         merge(arr[x], arr[2 * x + 1], arr[2 * x + 2]);
  123.     }
  124.  
  125.     stnode query(ll l, ll r, ll x, ll lx, ll rx) {
  126.         if (lx >= r || rx <= l) {
  127.             return NEUTRAL_STNODE;
  128.         }
  129.  
  130.         if (lx >= l && rx <= r) {
  131.             return arr[x];
  132.         }
  133.  
  134.         ll mid = (lx + rx) / 2;
  135.  
  136.         stnode curr;
  137.         stnode left = query(l, r, 2 * x + 1, lx, mid);
  138.         stnode right = query(l, r, 2 * x + 2, mid, rx);
  139.  
  140.         merge(curr, left, right);
  141.  
  142.         return curr;
  143.     }
  144.  
  145.     void build(vector<ll> &a, ll n) {
  146.         build(a, n, 0, 0, siz);
  147.     }
  148.  
  149.     void pupd(ll i, ll v) {
  150.         pupd(i, v, 0, 0, siz);
  151.     }
  152.  
  153.     stnode query(ll l, ll r) {
  154.         return query(l, r, 0, 0, siz);
  155.     }
  156. };
  157.  
  158. void solve()
  159. {
  160.     ll n, q; cin >> n >> q;
  161.     string s; cin >> s;
  162.     vector<ll> a(n);
  163.     for (ll i = 0; i < n; ++i) {
  164.         if (s[i] == '(') {
  165.             a[i] = 1;
  166.         }
  167.         else {
  168.             a[i] = -1;
  169.         }
  170.     }
  171.  
  172.     segtree st;
  173.     st.init(n);
  174.     st.build(a,n);
  175.  
  176.     while (q--) {
  177.         ll op, l, r; cin >> op >> l >> r;
  178.         l--, r--;
  179.  
  180.         if (op == 1) {
  181.             swap(a[l], a[r]);
  182.             st.pupd(l, a[l]);
  183.             st.pupd(r, a[r]);
  184.         }
  185.         else {
  186.             auto res = st.query(l, r + 1);
  187.             if (res.minpref >= 0 && res.sum == 0) {
  188.                 yes;
  189.             }
  190.             else {
  191.                 no;
  192.             }
  193.         }
  194.     }
  195. }
  196.  
  197. signed main()
  198. {
  199.     fastio;
  200.     solve();
  201.     return 0;
  202. }
Success #stdin #stdout 0.01s 5416KB
comments (?)
stdin
copy 
5 3
(())(
2 1 4
2 1 2
2 4 5
stdout
copy 
Yes
No
No
https://ideone.com/vOWOSN
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!