fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <assert.h>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> pii;
  9. typedef long long ll;
  10. typedef pair<ll, ll> pll;
  11.  
  12. const int MAX = 1e9+7;
  13. const int MIN = -1e9+7;
  14.  
  15. struct node{
  16. 	int key = 0;
  17. 	int p = 0; //priority
  18. 	int size = 1; //number of nodes in subtree
  19. 	int cost = (int) MIN;
  20. 	ll total_cost = (ll) MIN; //total of costs in subtree
  21. 	int max_cost = (int) MIN;
  22. 	int add = 0;
  23. 	node *left = NULL;
  24. 	node *right = NULL;
  25. 	node *parent = NULL;
  26. 	node(): left(NULL), right(NULL), parent(NULL){
  27. 		p = rand() % (int)MAX;
  28. 	}	
  29. 	node(int key): key(key), left(NULL), right(NULL), parent(NULL){
  30. 		p = rand() % (int)MAX;
  31. 	}
  32. 	node(int key, int cost): key(key), cost(cost), left(NULL), right(NULL), parent(NULL){
  33. 		p = rand() % (int)MAX;
  34. 		total_cost = (ll)cost;
  35. 		max_cost = cost;
  36. 	}
  37. 	static void set_right_parent(node *child, node *parent){
  38. 		if (parent == NULL) return;
  39. 		parent->right = child;
  40. 		if (child != NULL) child->parent = parent;
  41. 	}	
  42. 	static void set_left_parent(node *child, node *parent){
  43. 		if (parent == NULL) return;
  44. 		parent->left = child;
  45. 		if (child != NULL) child->parent = parent;
  46. 	}
  47. 	static void recalc(node *n){
  48. 		if (n == NULL) return;
  49. 		int total = 1;
  50. 		int total_cost = (ll)n->cost;
  51. 		int max_cost = n->cost;
  52. 		if (n->left != NULL){ 
  53. 			total += n->left->size;
  54. 			total_cost += n->left->total_cost;
  55. 			max_cost = max({max_cost, n->left->max_cost});
  56. 		}
  57. 		if (n->right != NULL){ 
  58. 			total += n->right->size;
  59. 			total_cost += n->right->total_cost;
  60. 			max_cost = max({max_cost, n->right->max_cost});
  61. 		}
  62. 		n->size = total;
  63. 		n->total_cost = total_cost;
  64. 		n->max_cost = max_cost;
  65. 	}
  66. 	static int sizeOf(node *n){
  67. 		if (n == NULL) return 0;
  68. 		else return n->size;
  69. 	}
  70. 	static void relay_add(node *n){
  71. 		if (n == NULL) return;
  72. 		n->cost += n->add;
  73. 		if (n->left != 0) n->left->add += n->add;
  74. 		if (n->right != 0) n->right->add += n->add;
  75. 		n->add = 0;
  76. 	}
  77. };
  78.  
  79. class Treap{
  80. public:
  81. 	Treap():root(NULL) {
  82. 	}
  83. 	Treap(node *root): root(root) {
  84. 	}
  85. 	~Treap() { }
  86. 	void insert(int x, int cost){
  87. 		node *l;
  88. 		node *r;
  89. 		Treap::split(root, x, l, r);
  90. 		node *n = new node(x, cost);
  91. 		root = Treap::merge(l, n);
  92. 		root = Treap::merge(root, r);
  93. 	}
  94. 	void remove(int x){
  95. 		node *l;
  96. 		node *r;
  97. 		Treap::split(root, x-1, l, r);
  98. 		node *ml;
  99. 		node *mr;
  100. 		Treap::split(r, x, ml, mr);
  101. 		root = Treap::merge(l, mr);
  102. 	}
  103. 	node* find_kth(int k){
  104. 		node *cur = root;
  105. 		while(cur != NULL){
  106. 			int size = node::sizeOf(cur->left);
  107. 			if (size == k){
  108. 				break;
  109. 			}
  110. 			else if (size > k){
  111. 				cur = cur->left;
  112. 			} else {
  113. 				cur = cur->right;
  114. 				k -= size + 1;
  115. 			}
  116. 		}
  117. 		return cur;
  118. 	}
  119. 	ll total_cost(int l, int r){
  120. 		node *fl;
  121. 		node *fr;
  122. 		Treap::split(root, l-1, fl, fr);
  123. 		node *ml;
  124. 		node *mr;
  125. 		Treap::split(fr, r, ml, mr);
  126. 		ll res = ml->total_cost + ml->add*ml->size;
  127. 		root = Treap::merge(ml, mr);
  128. 		root = Treap::merge(root, fl);
  129. 		return res;
  130. 	}	
  131. 	int max_cost(int l, int r){
  132. 		node *fl;
  133. 		node *fr;
  134. 		Treap::split(root, l-1, fl, fr);
  135. 		node *ml;
  136. 		node *mr;
  137. 		Treap::split(fr, r, ml, mr);
  138. 		ll res = ml->max_cost + ml->add;
  139. 		root = Treap::merge(ml, mr);
  140. 		root = Treap::merge(root, fl);
  141. 		return res;
  142. 	}
  143. 	void traverse(){
  144. 		inorder(root);
  145. 	}
  146. 	void add(int val, int l, int r){//add val to cost of each element in interval from l to r
  147. 		node *fl;
  148. 		node *fr;
  149. 		Treap::split(root, l-1, fl, fr);
  150. 		node *ml;
  151. 		node *mr;
  152. 		Treap::split(fr, r, ml, mr);
  153. 		ml->add = val;
  154. 		root = Treap::merge(ml, mr);
  155. 		root = Treap::merge(root, fl);		
  156. 	}
  157. private:
  158. 	node *root = NULL;
  159. 	static void split(node *cur, int key, node* &l, node* &r){
  160. 		if (cur == NULL) {
  161. 			l = NULL;
  162. 			r = NULL;
  163. 			return;
  164. 		}
  165. 		node::relay_add(cur);
  166. 		if (cur->key > key){
  167. 			node *newr = NULL;
  168. 			if (cur->left == NULL){
  169. 				l = NULL;
  170. 			}
  171. 			else {
  172. 				Treap::split(cur->left, key, l, newr);
  173. 			}	
  174. 			node::set_left_parent(newr, cur);
  175. 			r = cur;
  176. 			node::recalc(r);
  177. 		}
  178. 		else {
  179. 			node *newl = NULL;
  180. 			if (cur->right == NULL){
  181. 				r = NULL;
  182. 			}
  183. 			else {
  184. 				Treap::split(cur->right, key, newl, r);
  185. 			}
  186. 			node::set_right_parent(newl, cur);
  187. 			l = cur;
  188. 			node::recalc(l);
  189. 		}
  190. 	}
  191. 	static node* merge(node *l, node *r){
  192. 		if (l == NULL) return r;
  193. 		if (r == NULL) return l;
  194. 		if (l->key > r->key) swap(l, r);
  195. 		if (l->p > r->p){
  196. 			node::relay_add(l);
  197. 			node *right = Treap::merge(l->right, r);
  198. 			node::set_right_parent(right, l);
  199. 			node::recalc(l);
  200. 			return l;
  201. 		}
  202. 		else {
  203. 			node::relay_add(r);
  204. 			node *left = Treap::merge(l, r->left);
  205. 			node::set_left_parent(left, r);
  206. 			node::recalc(r);
  207. 			return r;
  208. 		}
  209. 		return NULL;
  210. 	}
  211. 	void inorder(node *cur){
  212. 		if (cur == NULL) return;
  213. 		inorder(cur->left);
  214. 		cout << cur->key << " size: " << cur->size  << " cost " << cur->cost << " total_cost " << cur->total_cost << " max_cost " << cur->max_cost << " add " << cur->add << endl;
  215. 		inorder(cur->right);
  216. 	}
  217. };
  218.  
  219. int main(int argc, char const *argv[])
  220. {
  221. 	ios::sync_with_stdio(false);
  222. 	Treap t;
  223. 	t.insert(0, 1);
  224. 	t.insert(1, 10);
  225. 	cout << t.max_cost(1, 1) << endl;
  226. 	t.insert(2, 40);
  227. 	t.insert(3, 20);
  228. 	cout << t.max_cost(0, 3) << endl;
  229. 	cout << t.max_cost(0, 2) << endl;
  230. 	cout << t.max_cost(0, 1) << endl;
  231. 	/* code */
  232. 	return 0;
  233. }
  234.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
Standard input is empty
stdout 
10
40
40
10
https://ideone.com/M9rnbg
language:
C++14 (gcc 8.3)
created:
7 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!