Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. void createTree();
  7.  
  8. void push(int curL, int curR, int left, int distance, bool color, int node);
  9.  
  10. void update(int curL, int curR, bool color, int node);
  11.  
  12. void propogate(int node, int curL, int curR, bool color);
  13.  
  14. int getParentNode(int node);
  15.  
  16. int leftChildren(int node);
  17.  
  18. int rightChildren(int node);
  19.  
  20. void pushUp(int node, int curL, int curR);
  21.  
  22. // False - white, True - black
  23. struct Node
  24. {
  25. bool upAndWeCorrectDownNo = false;
  26. bool color = false;
  27. int countBlackSegment = 0;
  28. int lengthBlack = 0;
  29. };
  30.  
  31. vector<Node> tree;
  32.  
  33. // ЭТО размер структуры, 2 в какой-то степени, на самом деле можно в раза уменьшить, если дальше в запросе изменить границы
  34. int SIZE = 2097152;
  35.  
  36. int main()
  37. {
  38. createTree();
  39. int n;
  40. cin >> n;
  41. char color;
  42. int left, distance;
  43. // Читаем запросы
  44. for (int i = 0; i < n; i++)
  45. {
  46. cin >> color;
  47. cin >> left >> distance;
  48. bool actualColor = (color == 'B');
  49. //Сам запрос первый два числа - границы отрезка за который отвечает вершина, в которой мы находимся
  50. // потом наши границы, дальше цвет и сама вершнина
  51. // Я ЖЕ КАК НЕНОРМАЛЬНЫЙ СТРОЯ ДЕРЕВЬЯ СНИЗУ
  52. // 7
  53. // 5 6
  54. // 1 2 3 4
  55. // Мне кажеться тебе прощу будет сделать с другой стороны
  56. push(0, (SIZE / 2), left + 500002, left + abs(distance) - 1l + 500002, actualColor, (SIZE - 1));
  57. //Вывожу ответ после запроса, он в вершнине
  58. cout << tree[SIZE - 1].countBlackSegment << " " << tree[SIZE - 1].lengthBlack << endl;
  59. }
  60. return 0;
  61. }
  62.  
  63.  
  64. void push(int curL, int curR, int left, int distance, bool color, int node)
  65. {
  66. // Если вне диапазоны - выходим
  67. if (curL > distance || curR < left)
  68. {
  69. return;
  70. }
  71. int midd = (curL + curR) / 2;
  72. // Если мы в вершине ниже которой всё неактуальное, а выше акутально, просто протоклнем в детей
  73. if (tree[node].upAndWeCorrectDownNo && node > (SIZE / 2))
  74. {
  75. propogate(leftChildren(node), curL, midd, tree[node].color);
  76. propogate(rightChildren(node), midd + 1, curR, tree[node].color);
  77. tree[node].upAndWeCorrectDownNo = false;
  78. }
  79. // Если мы попали на нужный нам отрезок, то делаем update
  80. if (left <= curL && curR <= distance)
  81. {
  82. update(curL, curR, color, node);
  83. return;
  84. }
  85. // Иначе дробимся далее
  86. push(curL, midd, left, distance, color, leftChildren(node));
  87. push(midd + 1, curR, left, distance, color, rightChildren(node));
  88. }
  89.  
  90. // ВОТ, тут важная часть началась
  91. // У меня в самом нижнем слое хранятся актальные данные!
  92. void update(int curL, int curR, bool color, int node)
  93. {
  94. // говорим, что ниже все не актуальное
  95. tree[node].upAndWeCorrectDownNo = true;
  96. // меняем цвет в вершине покрывающей подотрезок
  97. tree[node].color = color;
  98. // Меняем вершины на краях отрезка
  99. // Если это кажется нелогично, то представь что у нас нет дерева, и мы делаем такое просто на отрезке
  100. tree[curL].color = color;
  101. tree[curR].color = color;
  102. // В зависимости от цвета ставим кол-во черных на отрезке и их длинну
  103. if (color)
  104. {
  105. tree[node].lengthBlack = (curR - curL) + 1;
  106. tree[node].countBlackSegment = 1;
  107. }
  108. else
  109. {
  110. tree[node].lengthBlack = 0;
  111. tree[node].countBlackSegment = 0;
  112. }
  113. // Вот а теперь пропушиваем вверх, чтобы до вершины дошел правильный ответ
  114. pushUp(node, curL, curR);
  115. }
  116.  
  117. void pushUp(int node, int curL, int curR)
  118. {
  119. // Если мы в вершине выходим
  120. if (node == SIZE - 1)
  121. {
  122. return;
  123. }
  124. // Это будующие границы для родителя
  125. int newCurL, newCurR;
  126. if ((node % 2) == 1)
  127. { //left son он всегда нечетн
  128. int edge = (tree[curR].color && tree[curR + 1].color) ? -1 : 0; // Если границы с соседним отрезком черные, то кол-во отрезков = их сумме минус 1
  129. tree[getParentNode(node)].countBlackSegment = tree[node].countBlackSegment +
  130. tree[node + 1].countBlackSegment + edge;
  131. // Ставим длинну для родителя(просто сумма детей)
  132. tree[getParentNode(node)].lengthBlack = tree[node].lengthBlack +
  133. tree[node + 1].lengthBlack;
  134. newCurL = curL;
  135. newCurR = curR + (curR - curL) + 1;
  136. }
  137. else
  138. { //distance son он всегда четный
  139. int edge = (tree[curL - 1].color && tree[curL].color) ? -1 : 0; // Если границы с соседним отрезком черные, то кол-во отрезков = их сумме минус 1
  140. tree[getParentNode(node)].countBlackSegment = tree[node].countBlackSegment +
  141. tree[node - 1].countBlackSegment + edge;
  142. // Ставим длинну для родителя(просто сумма детей)
  143. tree[getParentNode(node)].lengthBlack = tree[node - 1].lengthBlack +
  144. tree[node].lengthBlack;
  145. newCurL = curL - (curR - curL) - 1;
  146. newCurR = curR;
  147. }
  148. //push up теперь переходим в родителя
  149. pushUp(getParentNode(node), newCurL, newCurR);
  150. }
  151.  
  152. // ну это просто обновление детей детей(протоклнули) (тут node - это нода одного из детей)
  153. void propogate(int node, int curL, int curR, bool color)
  154. {
  155. tree[node].upAndWeCorrectDownNo = true;
  156. tree[curL].color = color;
  157. tree[curR].color = color;
  158. tree[node].color = color;
  159. if (color)
  160. {
  161. tree[node].lengthBlack = (curR - curL) + 1;
  162. tree[node].countBlackSegment = 1;
  163. }
  164. else
  165. {
  166. tree[node].lengthBlack = 0;
  167. tree[node].countBlackSegment = 0;
  168. }
  169. }
  170.  
  171. void createTree()
  172. {
  173. tree.resize(SIZE);
  174. }
  175.  
  176. int getParentNode(int node)
  177. {
  178. int delta = SIZE - 1 - node;
  179. return SIZE - 1 - (delta - 1) / 2;
  180. }
  181.  
  182. int leftChildren(int node)
  183. {
  184. int delta = SIZE - 1 - node;
  185. return SIZE - 1 - (delta + 1) * 2;
  186. }
  187.  
  188. int rightChildren(int node)
  189. {
  190. int delta = SIZE - 1 - node;
  191. return SIZE - 1 - (delta) * 2 - 1;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement