fork download
  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
stdin
5 3
(())(
2 1 4
2 1 2
2 4 5
stdout
Yes
No
No