fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. struct node;
  6. node *newNode();
  7.  
  8.  
  9. struct node {
  10. 	long long lv, rv, sum;
  11. 	int count;
  12. 	node *left, *right;
  13. 	node() : left(NULL), right(NULL), count(0), sum(0) {}
  14.  
  15.  
  16. 	void extend() {
  17. 		if (!left) {
  18. 			long long m = (lv + rv) / 2;
  19. 			left = newNode();
  20. 			right = newNode();
  21. 			left->lv = lv;
  22. 			left->rv = m;
  23. 			right->lv = m + 1;
  24. 			right->rv = rv;
  25. 		}
  26. 	}
  27.  
  28.  
  29. 	long long getSum(long long l, long long r) {
  30. 		if (r < lv || rv < l || !sum) {
  31. 			return 0;
  32. 		}
  33.  
  34. 		if (l <= lv && rv <= r) {
  35. 			return sum;
  36. 		}
  37.  
  38. 		extend();
  39. 		return left->getSum(l, r) + right->getSum(l, r);
  40. 	}
  41.  
  42.  
  43. 	int getCount(long long l, long long r) {
  44. 		if (r < lv || rv < l || !count) {
  45. 			return 0;
  46. 		}
  47.  
  48. 		if (l <= lv && rv <= r) {
  49. 			return count;
  50. 		}
  51.  
  52. 		extend();
  53. 		return left->getCount(l, r) + right->getCount(l, r);
  54. 	}
  55.  
  56.  
  57. 	void add(long long newVal) {
  58. 		count++;
  59. 		sum += newVal;
  60.  
  61. 		if (lv < rv) {
  62. 			extend();
  63. 			(newVal <= left->rv ? left : right)->add(newVal);
  64. 		}
  65. 	}
  66.  
  67.  
  68. 	void remove(long long newVal) {
  69. 		count--;
  70. 		sum -= newVal;
  71.  
  72. 		if (lv < rv) {
  73. 			extend();
  74. 			(newVal <= left->rv ? left : right)->remove(newVal);
  75. 		}
  76. 	}
  77. };
  78.  
  79.  
  80. node *newNode() {
  81. 	static node buf[1111111];
  82. 	static int bufSize = 0;
  83. 	return &buf[bufSize++];
  84. }
  85.  
  86.  
  87. main() {
  88.  
  89. 	long long val;
  90. 	node *r = newNode();
  91. 	r->lv = 0;
  92. 	r->rv = 1e18;
  93.  
  94. 	///add val
  95. 	r->add(val);
  96. 	///remove val
  97. 	r->remove(val);
  98. 	///sum of elements greater than val
  99. 	r->getSum(val + 1, 1e18);
  100. 	///count of elements greater than val
  101. 	r->getCount(val + 1, 1e18);
  102.  
  103. }
  104.  
Success #stdin #stdout 0.02s 42208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5QoYzX
language:
C++14 (gcc 8.3)
created:
9 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!