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