fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template <class POINTER_TYPE, class TYPE> class segment_tree
  5. {
  6.     TYPE *SegmentTree;
  7.     POINTER_TYPE base_capacity = 0;
  8.     TYPE (*g)(TYPE, TYPE);
  9.     TYPE neutral;
  10.  
  11.     TYPE result_on_segment_in
  12.     (
  13.         POINTER_TYPE v, POINTER_TYPE tl,
  14.         POINTER_TYPE tr, POINTER_TYPE l,
  15.         POINTER_TYPE r
  16.     )
  17.     {
  18.         if (l > r) return neutral;
  19.         else if (l == tl && r == tr) return SegmentTree[v];
  20.         else
  21.         {
  22.             POINTER_TYPE tm = (tl + tr) / 2;
  23.             return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
  24.             result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
  25.         }
  26.     }
  27.  
  28.     void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
  29.     {
  30.         g = f;
  31.         neutral = neutr;
  32.         for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
  33.         {
  34.             NewTree[i] = neutral;
  35.         }
  36.         for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
  37.         {
  38.             NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
  39.         }
  40.         SegmentTree = NewTree;
  41.     }
  42.  
  43.     void fix_capacity(const POINTER_TYPE &base_array_size)
  44.     {
  45.         for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
  46.     }
  47.  
  48.     public:
  49.     void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)
  50.     {
  51.         fix_capacity(amount_of_elements);
  52.         TYPE *NewTree = new TYPE[base_capacity*2];
  53.         for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
  54.         {
  55.             NewTree[base_capacity+i] = preprocessing_function(i);
  56.         }
  57.         make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
  58.     }
  59.  
  60.     void assign(const POINTER_TYPE index, const TYPE new_value)
  61.     {
  62.         SegmentTree[base_capacity+index] = new_value;
  63.         for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
  64.         {
  65.             SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
  66.         }
  67.     }
  68.  
  69.     TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
  70.     {
  71.         return result_on_segment_in(1, 0, base_capacity-1, l, r);
  72.     }
  73. };
  74.  
  75. struct leaf
  76. {
  77. 	unsigned int number, amount;
  78. 	leaf()
  79. 	{
  80. 		number = 2000000;
  81. 		amount = 0;
  82. 	}
  83.  
  84. 	leaf(unsigned int a)
  85. 	{
  86. 		number = a, amount = 0;
  87. 	}
  88. };
  89.  
  90. leaf max_leafs(leaf a, leaf b)
  91. {
  92. 	return
  93. 	(a.amount == b.amount) ?
  94. 		(a.number < b.number) ? a : b
  95. 	:
  96. 		(a.amount > b.amount) ? a : b;
  97. }
  98.  
  99. leaf constructor(const unsigned int &i)
  100. {
  101. 	return leaf(i);
  102. }
  103.  
  104. int main()
  105. {
  106. 	segment_tree <unsigned int, leaf> box;
  107. 	box.read_and_construct(1000001, constructor, max_leafs, leaf());
  108.  
  109. 	unsigned int n, index;
  110. 	char operation;
  111. 	leaf tmp;
  112.  
  113. 	scanf("%u\n", &n); ++n;
  114. 	while (--n)
  115. 	{
  116. 		scanf("%c %u\n", &operation, &index);
  117. 		tmp = box.result_on_segment(index, index);
  118. 		if (operation == '+') ++tmp.amount;
  119. 		else --tmp.amount;
  120. 		box.assign(index, tmp);
  121. 		printf("%u\n", (box.result_on_segment(0, 1000000)).number);
  122. 	}
  123. 	return 0;
  124. }
Success #stdin #stdout 0.01s 31624KB
comments (?)
stdin
copy 
8
+ 71
+ 91
+ 99
+ 71
- 71
- 91
- 71
- 99
stdout
copy 
71
71
71
71
71
71
99
0
https://ideone.com/hkPAne
eo3358
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!