fork(11) download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <vector>
  10. #include <map>
  11. #include <sstream>
  12. #include <cmath>
  13. #include <limits>
  14. #include <utility>
  15. #include <iomanip>
  16. #include <set>
  17. #include <numeric>
  18. #include <cassert>
  19. #include <ctime>
  20.  
  21. #define INF_MAX 2147483647
  22. #define INF_MIN -2147483647
  23. #define INF_LL 9223372036854775807LL
  24. #define INF 2000000000
  25. #define PI acos(-1.0)
  26. #define EPS 1e-8
  27. #define LL long long
  28. #define mod 1000000007
  29. #define pb push_back
  30. #define mp make_pair
  31. #define f first
  32. #define s second
  33. #define setzero(a) memset(a,0,sizeof(a))
  34. #define setdp(a) memset(a,-1,sizeof(a))
  35. #define bits(a) __builtin_popcount(a)
  36.  
  37. using namespace std;
  38.  
  39. int tree[400005][27], lazy[400005][27];
  40. char s[100005];
  41.  
  42. void build(int i,int L,int R)
  43. {
  44. if(L == R)
  45. {
  46. tree[i][s[L] - 'a'] = 1;
  47. for(int j=0;j<26;j++)
  48. lazy[i][j] = -1;
  49. return ;
  50. }
  51. build(i*2 + 1, L, (L + R) / 2);
  52. build(i*2 + 2, (L + R) / 2 + 1, R);
  53. for(int j=0;j<26;j++)
  54. {
  55. lazy[i][j] = -1;
  56. tree[i][j] = tree[i*2 + 1][j] + tree[i*2 + 2][j];
  57. }
  58. }
  59.  
  60. void update(int i, int L, int R, int x, int y, int val, int j)
  61. {
  62. if(lazy[i][j] != -1)
  63. {
  64. tree[i][j] = lazy[i][j] * (R - L + 1);
  65. if(L != R)
  66. {
  67. lazy[i*2+1][j] = lazy[i][j];
  68. lazy[i*2+2][j] = lazy[i][j];
  69. }
  70. lazy[i][j] = -1;
  71. }
  72. if(L >= x && R <= y)
  73. {
  74. lazy[i][j] = val;
  75. tree[i][j] = lazy[i][j] * (R - L + 1);
  76. if(L != R)
  77. {
  78. lazy[i*2+1][j] = lazy[i][j];
  79. lazy[i*2+2][j] = lazy[i][j];
  80. }
  81. lazy[i][j] = -1;
  82. return;
  83. }
  84. if(L > y || R < x)
  85. return;
  86. update(i*2 + 1, L, (L + R) / 2, x, y, val, j);
  87. update(i*2 + 2, (L + R) / 2 + 1, R, x, y, val, j);
  88. tree[i][j] = tree[i*2 + 1][j] + tree[i*2 + 2][j];
  89. }
  90.  
  91. int query(int i, int L, int R, int x, int y, int j)
  92. {
  93. if(lazy[i][j] != -1)
  94. {
  95. tree[i][j] = lazy[i][j] * (R - L + 1);
  96. if(L != R)
  97. {
  98. lazy[i*2+1][j] = lazy[i][j];
  99. lazy[i*2+2][j] = lazy[i][j];
  100. }
  101. lazy[i][j] = -1;
  102. }
  103. if(L >= x && R <= y)
  104. return tree[i][j];
  105. if(L > y || R < x)
  106. return 0;
  107. return query(i*2 + 1, L, (L + R) / 2, x, y, j) + query(i*2 + 2, (L + R) / 2 + 1, R, x, y, j);
  108. }
  109.  
  110. void get(int i, int L, int R, int j)
  111. {
  112. if(lazy[i][j] != -1)
  113. {
  114. tree[i][j] = lazy[i][j] * (R - L + 1);
  115. if(L != R)
  116. {
  117. lazy[i*2+1][j] = lazy[i][j];
  118. lazy[i*2+2][j] = lazy[i][j];
  119. }
  120. lazy[i][j] = -1;
  121. }
  122. if(!tree[i][j])
  123. return ;
  124. if(L == R)
  125. {
  126. s[L] = j + 'a';
  127. return;
  128. }
  129. get(i*2 + 1, L, (L + R) / 2, j);
  130. get(i*2 + 2, (L + R) / 2 + 1, R, j);
  131. }
  132.  
  133. int cnt[26];
  134.  
  135. int main()
  136. {
  137. //ios_base::sync_with_stdio(0);
  138. //freopen("test0.txt", "r", stdin);
  139. //freopen("lca.out", "w", stdout);
  140. int n, q, x, y, up;
  141. scanf("%d %d", &n, &q);
  142. scanf("%s", s);
  143. build(0, 0, n - 1);
  144. for(int i=0;i<q;i++)
  145. {
  146. scanf("%d %d %d", &x, &y, &up);
  147. x--, y--;
  148. for(int j=0;j<26;j++)
  149. cnt[j] = query(0, 0, n - 1, x, y, j);
  150. int curr = x;
  151. if(!up) curr = y;
  152. for(int j=0;j<26;j++)
  153. {
  154. if(!cnt[j]) continue;
  155. update(0, 0, n - 1, x, y, 0, j);
  156. if(up)
  157. {
  158. update(0, 0, n - 1, curr, curr + cnt[j] - 1, 1, j);
  159. curr+=cnt[j];
  160. }
  161. else
  162. {
  163. update(0, 0, n - 1, curr - cnt[j] + 1, curr, 1, j);
  164. curr-=cnt[j];
  165. }
  166. }
  167. }
  168. for(int i=0;i<26;i++)
  169. get(0, 0, n - 1, i);
  170. printf("%s", s);
  171. return 0;
  172. }
Success #stdin #stdout 0s 87616KB
stdin
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
stdout
cbcaaaabdd