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

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!