fork download
copy 
  1. // Success consists of going from failure to failure without loss of enthusiasm
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define nl '\n'
  7.  
  8. mt19937 rng(1008);
  9. const int MX = 2e5;
  10. const int MOD = 1e9 + 7, base = 37;
  11. vector<int> pows = {1};
  12.  
  13. // treap node
  14. struct node {
  15. 	int val, pri, sz = 1;
  16. 	int hash, rhash; // left to right hash, and right to left (reversed) hash
  17. 	node *left, *right;
  18.  
  19. 	node(int v) {
  20. 		hash = rhash = val = v; // initalize hashes and value of node
  21. 		pri = (rng() % MOD); // set priority of the node
  22. 		left = right = NULL; // set children to null
  23. 	}
  24. };
  25.  
  26. // getter methods
  27. int get_size(node* t) { return t ? t->sz : 0; };
  28. int get_hash(node* t) { return t ? t->hash : 0; };
  29. int get_rhash(node* t) { return t ? t->rhash : 0; };
  30.  
  31. // function to combine hashs
  32. int combine_hash(int hasha, int hashb, int blen) {
  33. 	return ((hasha * 1LL * pows[blen]) % MOD + hashb) % MOD;
  34. }
  35.  
  36. node* comp(node* t) {
  37. 	if (t == NULL) return t;
  38. 	// maintaining the size of the treap
  39. 	t->sz = 1 + get_size(t->left) + get_size(t->right);
  40.  
  41. 	// maintaining left to right hash
  42. 	t->hash = get_hash(t->left);
  43. 	t->hash = combine_hash(t->hash, t->val, 1);
  44. 	t->hash = combine_hash(t->hash, get_hash(t->right), get_size(t->right));
  45.  
  46. 	// maintaining right to left hash
  47. 	t->rhash = get_rhash(t->right);
  48. 	t->rhash = combine_hash(t->rhash, t->val, 1);
  49. 	t->rhash = combine_hash(t->rhash, get_rhash(t->left), get_size(t->left));
  50. 	return t;
  51. }
  52.  
  53. // merge two treaps (l is to the left of r)
  54. node* merge(node* l, node* r) { 
  55. 	// if one of the nodes is null, return the other
  56. 	if (!l || !r) return l ? l : r;
  57.  
  58. 	// whichever is higher priority is the root
  59. 	if (l->pri > r->pri) {
  60. 		// l is root, merge right child with r
  61. 		l->right = merge(l->right, r);
  62. 		return comp(l);
  63. 	} else {
  64. 		// r is root, merge left child with l
  65. 		r->left = merge(l, r->left);
  66. 		return comp(r);
  67. 	}	
  68. }
  69.  
  70. // split treap into 2 -> with "amount" nodes in the left half
  71. pair<node*, node*> split_by_amount(node* t, int amount) { 
  72. 	if (t == NULL) return {t, t};
  73.  
  74. 	// if left child has enough nodes, then recurse on left child
  75. 	if (get_size(t->left) >= amount) {
  76. 		auto [l, r] = split_by_amount(t->left, amount);
  77. 		t->left = r; // left child will become the excess from the split
  78. 		return {l, comp(t)};	
  79. 	} else { // otherwise, recurse on right child (taking all the nodes to the left)
  80. 		auto [l, r] = split_by_amount(t->right, amount - get_size(t->left) - 1);
  81. 		t->right = l; // right child will become the part taken from the right subtree
  82. 		return {comp(t), r};
  83. 	}
  84. }
  85.  
  86. // split treap into 2 -> with values with < v and >= v separately
  87. pair<node*, node*> split_by_value(node* t, int v) { 
  88. 	if (t == NULL) return {t, t};
  89.  
  90. 	// if it is greater or equal to the value, then everything in the right child is larger too
  91. 	if (t->val >= v) {
  92. 		// recurse on the left child
  93. 		auto [l, r] = split_by_value(t->left, v);
  94. 		t->left = r; // left child becomes the part not taken from the left child
  95. 		return {l, comp(t)};	
  96. 	} else { // otherwise, everything in the left subtree (and this node) is taken
  97. 		// recurse on the right subtree
  98. 		auto [l, r] = split_by_value(t->right, v);
  99. 		t->right = l; // right child becomes the part taken from the right child
  100. 		return {comp(t), r};
  101. 	}
  102. }
  103.  
  104. int main() {
  105. 	cin.tie(0)->sync_with_stdio(0);
  106.  
  107. 	// building array of powers of base (for hashing)
  108. 	for(int i = 0; i < MX; i++) 
  109. 		pows.push_back((pows.back() * 1LL * base) % MOD);
  110.  
  111.  
  112. 	int N, Q; cin >> N >> Q;
  113.  
  114. 	node* T = NULL;
  115. 	for(int i = 0; i < N; i++) {
  116. 		char c; cin >> c;
  117. 		// building treap
  118. 		T = merge(T, new node(c - 'a' + 1));
  119. 	}
  120.  
  121. 	while(Q--) {
  122. 		int t; cin >> t; --t;
  123.  
  124. 		if (t == 0) {
  125. 			int l, r; cin >> l >> r; --l, --r;
  126. 			// split first l elements from rest
  127. 			auto [L, M] = split_by_amount(T, l);
  128. 			// split first r elements from rest
  129. 			auto [m, R] = split_by_amount(M, r - l + 1);
  130.  
  131. 			// merge elements before l and elements after r
  132. 			T = merge(L, R);
  133. 		}
  134.  
  135. 		if (t == 1) {
  136. 			int p; char c; cin >> c >> p; --p;
  137. 			// split first p elements from rest
  138. 			auto [L, R] = split_by_amount(T, p);
  139. 			// merge first p elements with a node with a value of c
  140. 			// then merge with rest of treap
  141. 			T = merge(L, merge(new node(c - 'a' + 1), R));
  142. 		}
  143.  
  144. 		if (t == 2) {
  145. 			int l, r; cin >> l >> r; --l, --r;
  146. 			// split first l elements from rest
  147. 			auto [L, M] = split_by_amount(T, l);
  148. 			// split first r elements from rest
  149. 			auto [m, R] = split_by_amount(M, r - l + 1);
  150.  
  151. 			// m is the treap that corresponds to the range [l, r] in the string
  152. 			// check if the left to right hash is equal to the right to left hash
  153. 			bool pali = get_hash(m) == get_rhash(m);
  154. 			T = merge(L, merge(m, R));
  155.  
  156. 			cout << (pali ? "yes" : "no") << nl;
  157. 		}
  158. 	}	
  159.  
  160.  
  161. 	exit(0-0);
  162. }
  163.  
  164. // Breathe In, Breathe Out
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dk4pKH
language:
C++ (gcc 8.3)
created:
3 days 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!