fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const int MAXN = 2e5 + 5;
  7. const ll BASE = 31, MOD = 1e9 + 7;
  8.  
  9. int num(char c){ return c - 'a' + 1; }
  10.  
  11. typedef struct nd{
  12. ll hashn, hashr;
  13. int cnt, pr, rev;
  14. ll val;
  15. nd *l, *r;
  16. nd(char c) : hashn(num(c)), hashr(num(c)), cnt(1), pr(rand()), rev(0), val(num(c)), l(0), r(0){}
  17. } *node;
  18.  
  19. node root;
  20. char str[MAXN];
  21. ll powers[MAXN];
  22. int N, M;
  23.  
  24. int cnt(node t){ return t ? t->cnt : 0; }
  25. ll nhash(node t){ return t ? t->hashn : 0; }
  26. ll rhash(node t){ return t ? t->hashr : 0; }
  27. int rev(node t){ return t ? t->rev : 0; }
  28. int val(node t){ return t ? t->val : 0; }
  29. ll mod(ll x){ return x % MOD; }
  30.  
  31. void upd(node &t){
  32.  
  33. if(t){
  34.  
  35. if(t->rev){
  36. swap(t->l, t->r);
  37. swap(t->hashn, t->hashr);
  38. if(t->l){
  39. t->l->rev ^= 1;
  40. }
  41. if(t->r){
  42. t->r->rev ^= 1;
  43. }
  44. t->rev = 0;
  45. }
  46. }
  47. }
  48.  
  49. void operation(node &t)
  50. {
  51. if(!t) return;
  52.  
  53. upd(t->l);
  54. upd(t->r);
  55.  
  56. t->cnt = cnt(t->l) + cnt(t->r) + 1;
  57. t->hashn = mod(mod(nhash(t->l) + mod(powers[cnt(t->l)] * val(t))) + mod(powers[cnt(t->l) + 1] * nhash(t->r)));
  58. t->hashr = mod(mod(rhash(t->r) + mod(powers[cnt(t->r)] * val(t))) + mod(powers[cnt(t->r) + 1] * rhash(t->l)));
  59.  
  60.  
  61. }
  62.  
  63. void split(node t, node &l, node &r, int key){
  64. upd(t);
  65. if(!t){ l = r = 0; return; }
  66. if(cnt(t->l) + 1 <= key){ split(t->r, t->r, r, key - cnt(t->l) - 1); l = t; }
  67. else{ split(t->l, l, t->l, key); r = t; }
  68. operation(l); operation(r);
  69. }
  70.  
  71. void merge(node &t, node l, node r){
  72. upd(l); upd(r);
  73. if(!l || !r){ t = l ? l : r; return; }
  74. if(l->pr > r->pr){ merge(l->r, l->r, r); t = l; }
  75. else{ merge(r->l, l, r->l); t = r; }
  76. operation(t);
  77. }
  78.  
  79. bool check(node t, int l, int r){
  80. node t1, t2, t3;
  81. split(t, t1, t2, r);
  82. split(t1, t3, t1, l - 1);
  83. bool res = (t1->hashn == t1->hashr);
  84. merge(t1, t3, t1);
  85. merge(t, t1, t2);
  86. return res;
  87. }
  88.  
  89. void add(node &t, node x, int pos){
  90. node t1, t2;
  91. split(t, t1, t2, pos - 1);
  92. merge(t1, t1, x);
  93. merge(t, t1, t2);
  94. }
  95.  
  96. void reverse(node &t, int l, int r){
  97. node t1, t2, t3;
  98. split(t, t1, t2, r);
  99. split(t1, t3, t1, l - 1);
  100. t1->rev ^= 1;
  101. merge(t1, t3, t1);
  102. merge(t, t1, t2);
  103. }
  104.  
  105. void cut(node &t, int i, int j, int k){
  106. node t1, t2, t3, t4, t5;
  107. split(t, t1, t3, j);
  108. split(t1, t1, t2, i - 1);
  109. merge(t1, t1, t3);
  110. split(t1, t4, t5, k);
  111. merge(t4, t4, t2);
  112. merge(t, t4, t5);
  113. }
  114.  
  115. int main(){
  116. scanf("%d %d %s", &N, &M, str);
  117. powers[0] = 1;
  118. for(int i=1; i<MAXN; ++i) powers[i] = mod(powers[i - 1] * BASE);
  119. for(int i=0; i<N; ++i) merge(root, root, new nd(str[i]));
  120. while(M--){
  121. char s[3], q[3];
  122. int x, y, z, k;
  123. scanf("%s %d %d", s, &x, &y);
  124. if(s[0] == 'Q') puts(check(root, x, y) ? "YES" : "NO");
  125. else if(x == 1){
  126. scanf("%d %d", &z, &k); cut(root, y, z, k);
  127. }
  128. else if(x == 2){
  129. scanf("%d", &z); reverse(root, y, z);
  130. }
  131. else{
  132. scanf("%s", q); add(root, new nd(q[0]), y);
  133. }
  134. }
  135. return 0;
  136. }
Success #stdin #stdout 0s 4612KB
stdin
Standard input is empty
stdout
Standard output is empty