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.  
  10. const int MX = 2e5;
  11. const int MOD = 1e9 + 7;
  12. const int base = 37;
  13.  
  14. vector<int> pows = {1};
  15.  
  16.  
  17. // treap node
  18. struct node {
  19. 	int val, pri, sz = 1;
  20. 	long long sum; // sum of values in the treap
  21.  
  22. 	// (propagated value)
  23. 	bool flip; // whether this node should be reversed
  24.  
  25. 	node *left, *right;
  26.  
  27. 	node(int v) {
  28. 		sum = val = v; // set sum and val to the value of the node
  29. 		flip = 0; // default to no reversals needed
  30. 		pri = (rng() % MOD); // set priority of node
  31. 		left = right = NULL; // set children to null
  32. 	}
  33. };
  34.  
  35. // getter methods
  36. int get_size(node* t) { return t ? t->sz : 0; };
  37. long long get_sum(node* t) { return t ? t->sum : 0; };
  38.  
  39. void prop(node* t) {
  40. 	if (!t || !t->flip) return; // if nothing to propagate
  41.  
  42. 	swap(t->left, t->right); // perform the flip
  43.  
  44. 	// propagate to left child (if it exists)
  45. 	if (t->left) t->left->flip ^= 1; 
  46.  
  47. 	// propagate to right child (if it exists)
  48. 	if (t->right) t->right->flip ^= 1; 
  49.  
  50. 	t->flip = 0; // reset flip value (reversal was performed)
  51. }
  52.  
  53. node* comp(node* t) {
  54. 	if (t == NULL) return t;
  55. 	prop(t->left); prop(t->right); // propagate to children
  56.  
  57. 	// maintain the treap's size
  58. 	t->sz = 1 + get_size(t->left) + get_size(t->right);
  59.  
  60. 	// maintain the sum of values in the treap
  61. 	t->sum = t->val + get_sum(t->left) + get_sum(t->right);
  62. 	return t;
  63. }
  64.  
  65. // merge two treaps (l is to the left of r)
  66. node* merge(node* l, node* r) { 
  67. 	// if one of the nodes is null, return the other
  68. 	if (!l || !r) return l ? l : r;
  69.  
  70. 	prop(l); prop(r);
  71. 	// whichever is higher priority is the root
  72. 	if (l->pri > r->pri) {
  73. 		// l is root, merge right child with r
  74. 		l->right = merge(l->right, r);
  75. 		return comp(l);
  76. 	} else {
  77. 		// r is root, merge left child with l
  78. 		r->left = merge(l, r->left);
  79. 		return comp(r);
  80. 	}	
  81. }
  82.  
  83. // split treap into 2 -> "amount" nodes in the left half
  84. pair<node*, node*> split_by_amount(node* t, int amount) { 
  85. 	if (t == NULL) return {t, t};
  86.  
  87. 	prop(t);
  88. 	if (get_size(t->left) >= amount) {
  89. 		auto [l, r] = split_by_amount(t->left, amount);
  90. 		t->left = r;
  91. 		return {l, comp(t)};	
  92. 	} else {
  93. 		auto [l, r] = split_by_amount(t->right, amount - get_size(t->left) - 1);
  94. 		t->right = l;
  95. 		return {comp(t), r};
  96. 	}
  97. }
  98.  
  99. // split treap into 2 -> values with < v and >= v
  100. // pair<node*, node*> split_by_value(node* t, int v) { 
  101. // 	if (t == NULL) return {t, t};
  102.  
  103. // 	if (t->val >= v) {
  104. // 		auto [l, r] = split_by_value(t->left, v);
  105. // 		t->left = r;
  106. // 		return {l, comp(t)};	
  107. // 	} else {
  108. // 		auto [l, r] = split_by_value(t->right, v);
  109. // 		t->right = l;
  110. // 		return {comp(t), r};
  111. // 	}
  112. // }
  113.  
  114.  
  115.  
  116. int main() {
  117. 	cin.tie(0)->sync_with_stdio(0);
  118.  
  119.  
  120. 	int N, Q; cin >> N >> Q;
  121.  
  122. 	node* T = NULL;
  123. 	for(int i = 0; i < N; i++) {
  124. 		int x; cin >> x;
  125. 		// build treap
  126. 		T = merge(T, new node(x));
  127. 	}
  128.  
  129. 	while(Q--) {
  130. 		int t; cin >> t; --t;
  131.  
  132. 		if (t == 0) {
  133. 			int l, r; cin >> l >> r; --l, --r;
  134. 			auto [L, M] = split_by_amount(T, l);
  135. 			auto [m, R] = split_by_amount(M, r - l + 1);
  136.  
  137. 			// obtain the treap for [l, r]
  138. 			m->flip ^= 1; // update flip value for root
  139.  
  140. 			// return treap to original state
  141. 			T = merge(L, merge(m, R));
  142. 		}
  143.  
  144. 		if (t == 1) {
  145. 			int l, r; cin >> l >> r; --l, --r;
  146. 			auto [L, M] = split_by_amount(T, l);
  147. 			auto [m, R] = split_by_amount(M, r - l + 1);
  148.  
  149. 			// obtain the treap for [l, r]
  150. 			cout << m->sum << nl; // output sum of values in treap
  151.  
  152. 			// return treap to original state
  153. 			T = merge(L, merge(m, R)); 
  154. 		}
  155. 	}	
  156.  
  157.  
  158. 	exit(0-0);
  159. }
  160.  
  161. // Breathe In, Breathe Out
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8DZ9WO
language:
C++ (gcc 8.3)
created:
1 day 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!