fork download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <array>
  6. #include <tuple>
  7. using namespace std;
  8. #define SZ(a) (int)(a).size()
  9. typedef long long ll;
  10.  
  11. typedef char E;
  12.  
  13. struct nd {
  14. typedef nd* ndp;
  15. E e;
  16. ndp p;
  17. array<ndp, 2> c;
  18. bool rev;
  19. int sz;
  20. E shift;
  21. nd(E _e, ndp _p);
  22. };
  23. typedef nd* ndp;
  24.  
  25. ndp root;
  26.  
  27. bool isroot(ndp t) {
  28. return t == root;
  29. }
  30.  
  31. bool isleaf(ndp t) {
  32. return t == NULL;
  33. }
  34.  
  35. int getsz(ndp t) {
  36. return isleaf(t) ? 0 : t->sz;
  37. }
  38.  
  39. nd::nd(E _e, ndp _p) {
  40. e = _e;
  41. p = _p;
  42. rev = false;
  43. shift = 0;
  44. }
  45.  
  46. bool ic(ndp x) {
  47. auto y = x->p;
  48. return x == y->c[1];
  49. }
  50.  
  51. void apply_lazy(ndp x) {
  52. for (auto i = 0; i < 2; i++) {
  53. auto w = x->c[i];
  54. if (!isleaf(w)) {
  55. w->shift = (w->shift+x->shift)%26;
  56. w->rev ^= x->rev;
  57. }
  58. }
  59. x->e = (x->e+x->shift)%26;;
  60. x->shift = 0;
  61. if (x->rev) {
  62. swap(x->c[0], x->c[1]);
  63. x->rev = false;
  64. }
  65. }
  66.  
  67. void rot(ndp y, int i) {
  68. auto z = y->p;
  69. auto x = y->c[i];
  70. z->c[ic(y)] = x;
  71. x->p = z;
  72. z = x->c[i ^ 1];
  73. x->c[i ^ 1] = y;
  74. y->p = x;
  75. y->c[i] = z;
  76. if (!isleaf(z)) {
  77. z->p = y;
  78. }
  79. x->sz = y->sz;
  80. y->sz = getsz(y->c[0])+1+getsz(y->c[1]);
  81. }
  82.  
  83. void splay(ndp x) {
  84. while (true) {
  85. auto y = x->p;
  86. if (isroot(y)) {
  87. break;
  88. }
  89. auto i = ic(x);
  90. auto z = y->p;
  91. if (isroot(z)) {
  92. rot(y, i);
  93. break;
  94. }
  95. auto j = ic(y);
  96. if (i == j) {
  97. rot(z, j);
  98. rot(y, i);
  99. }
  100. else {
  101. rot(y, i);
  102. rot(z, j);
  103. }
  104. }
  105. }
  106.  
  107. void at(ndp& t, int i) {
  108. while (true) {
  109. apply_lazy(t);
  110. auto szl = getsz(t->c[0]);
  111. if (i == szl) {
  112. break;
  113. }
  114. else if (i > szl) {
  115. t = t->c[1];
  116. i -= szl+1;
  117. }
  118. else {
  119. t = t->c[0];
  120. }
  121. }
  122. splay(t);
  123. }
  124.  
  125. pair<ndp, bool> subtree(ndp& t, int l, int r) {
  126. at(t, r);
  127. auto x = t->c[0];
  128. root = t;
  129. at(x, l-1);
  130. root = t->p;
  131. return {x, 1};
  132. }
  133.  
  134. ndp cut(ndp& t, int l, int r) {
  135. ndp y;
  136. bool b;
  137. tie(y, b) = subtree(t, l, r);
  138. auto x = y->c[b];
  139. y->c[b] = NULL;
  140. if (!isleaf(x)) {
  141. x->p = root;
  142. }
  143. for (; !isroot(y); y = y->p) {
  144. y->sz -= getsz(x);
  145. }
  146. return x;
  147. }
  148.  
  149. void paste(ndp& t, int i, ndp x) {
  150. ndp y;
  151. bool b;
  152. tie(y, b) = subtree(t, i, i);
  153. y->c[b] = x;
  154. if (!isleaf(x)) {
  155. x->p = y;
  156. }
  157. for (; !isroot(y); y = y->p) {
  158. y->sz += getsz(x);
  159. }
  160. }
  161.  
  162. ndp mkTree(string::iterator l, string::iterator r, ndp p, string indent = "") {
  163. if (l == r) {
  164. return NULL;
  165. }
  166. auto d = r-l;
  167. auto m = l+d/2;
  168. auto t = new nd(*m-'a', p);
  169. auto indent1 = indent+" ";
  170. t->c[0] = mkTree(l, m, t, indent1);
  171. t->c[1] = mkTree(m+1, r, t, indent1);
  172. t->sz = getsz(t->c[0])+1+getsz(t->c[1]);
  173. return t;
  174. }
  175.  
  176. string inorder(ndp t) {
  177. if (isleaf(t)) {
  178. return "";
  179. }
  180. apply_lazy(t);
  181. return inorder(t->c[0])+(char)('a'+t->e)+inorder(t->c[1]);
  182. }
  183.  
  184. int main() {
  185. cin.sync_with_stdio(false);
  186. string s;
  187. cin >> s;
  188. s = "a"+s+"a";
  189. root = new nd(0, NULL);
  190. auto t = mkTree(begin(s), end(s), root);
  191. int nq;
  192. cin >> nq;
  193. for (auto iq = 0; iq < nq; iq++) {
  194. int o;
  195. cin >> o;
  196. if (o == 1) {
  197. int l, r, p;
  198. cin >> l >> r >> p;
  199. l--;
  200. l++; r++; p++;
  201. auto x = cut(t, l, r);
  202. paste(t, p, x);
  203. }
  204. else if (o == 2) {
  205. int l, r, c;
  206. cin >> l >> r >> c;
  207. l--;
  208. l++; r++;
  209. ndp y;
  210. bool b;
  211. tie(y, b) = subtree(t, l, r);
  212. auto x = y->c[b];
  213. if (!isleaf(x)) {
  214. x->shift = (x->shift+c)%26;
  215. }
  216. }
  217. else {
  218. int l, r;
  219. cin >> l >> r;
  220. l--;
  221. l++; r++;
  222. ndp y;
  223. bool b;
  224. tie(y, b) = subtree(t, l, r);
  225. auto x = y->c[b];
  226. if (!isleaf(x)) {
  227. x->rev = !x->rev;
  228. }
  229. }
  230. }
  231. auto ans = inorder(t);
  232. ans = string(begin(ans)+1, end(ans)-1);
  233. puts(ans.c_str());
  234. return 0;
  235. }
  236.  
Success #stdin #stdout 0s 15248KB
stdin
Standard input is empty
stdout