fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JQinjW
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!