Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- void createTree();
- void push(int curL, int curR, int left, int distance, bool color, int node);
- void update(int curL, int curR, bool color, int node);
- void propogate(int node, int curL, int curR, bool color);
- int getParentNode(int node);
- int leftChildren(int node);
- int rightChildren(int node);
- void pushUp(int node, int curL, int curR);
- // False - white, True - black
- struct Node
- {
- bool upAndWeCorrectDownNo = false;
- bool color = false;
- int countBlackSegment = 0;
- int lengthBlack = 0;
- };
- vector<Node> tree;
- // ЭТО размер структуры, 2 в какой-то степени, на самом деле можно в раза уменьшить, если дальше в запросе изменить границы
- int SIZE = 2097152;
- int main()
- {
- createTree();
- int n;
- cin >> n;
- char color;
- int left, distance;
- // Читаем запросы
- for (int i = 0; i < n; i++)
- {
- cin >> color;
- cin >> left >> distance;
- bool actualColor = (color == 'B');
- //Сам запрос первый два числа - границы отрезка за который отвечает вершина, в которой мы находимся
- // потом наши границы, дальше цвет и сама вершнина
- // Я ЖЕ КАК НЕНОРМАЛЬНЫЙ СТРОЯ ДЕРЕВЬЯ СНИЗУ
- // 7
- // 5 6
- // 1 2 3 4
- // Мне кажеться тебе прощу будет сделать с другой стороны
- push(0, (SIZE / 2), left + 500002, left + abs(distance) - 1l + 500002, actualColor, (SIZE - 1));
- //Вывожу ответ после запроса, он в вершнине
- cout << tree[SIZE - 1].countBlackSegment << " " << tree[SIZE - 1].lengthBlack << endl;
- }
- return 0;
- }
- void push(int curL, int curR, int left, int distance, bool color, int node)
- {
- // Если вне диапазоны - выходим
- if (curL > distance || curR < left)
- {
- return;
- }
- int midd = (curL + curR) / 2;
- // Если мы в вершине ниже которой всё неактуальное, а выше акутально, просто протоклнем в детей
- if (tree[node].upAndWeCorrectDownNo && node > (SIZE / 2))
- {
- propogate(leftChildren(node), curL, midd, tree[node].color);
- propogate(rightChildren(node), midd + 1, curR, tree[node].color);
- tree[node].upAndWeCorrectDownNo = false;
- }
- // Если мы попали на нужный нам отрезок, то делаем update
- if (left <= curL && curR <= distance)
- {
- update(curL, curR, color, node);
- return;
- }
- // Иначе дробимся далее
- push(curL, midd, left, distance, color, leftChildren(node));
- push(midd + 1, curR, left, distance, color, rightChildren(node));
- }
- // ВОТ, тут важная часть началась
- // У меня в самом нижнем слое хранятся актальные данные!
- void update(int curL, int curR, bool color, int node)
- {
- // говорим, что ниже все не актуальное
- tree[node].upAndWeCorrectDownNo = true;
- // меняем цвет в вершине покрывающей подотрезок
- tree[node].color = color;
- // Меняем вершины на краях отрезка
- // Если это кажется нелогично, то представь что у нас нет дерева, и мы делаем такое просто на отрезке
- tree[curL].color = color;
- tree[curR].color = color;
- // В зависимости от цвета ставим кол-во черных на отрезке и их длинну
- if (color)
- {
- tree[node].lengthBlack = (curR - curL) + 1;
- tree[node].countBlackSegment = 1;
- }
- else
- {
- tree[node].lengthBlack = 0;
- tree[node].countBlackSegment = 0;
- }
- // Вот а теперь пропушиваем вверх, чтобы до вершины дошел правильный ответ
- pushUp(node, curL, curR);
- }
- void pushUp(int node, int curL, int curR)
- {
- // Если мы в вершине выходим
- if (node == SIZE - 1)
- {
- return;
- }
- // Это будующие границы для родителя
- int newCurL, newCurR;
- if ((node % 2) == 1)
- { //left son он всегда нечетн
- int edge = (tree[curR].color && tree[curR + 1].color) ? -1 : 0; // Если границы с соседним отрезком черные, то кол-во отрезков = их сумме минус 1
- tree[getParentNode(node)].countBlackSegment = tree[node].countBlackSegment +
- tree[node + 1].countBlackSegment + edge;
- // Ставим длинну для родителя(просто сумма детей)
- tree[getParentNode(node)].lengthBlack = tree[node].lengthBlack +
- tree[node + 1].lengthBlack;
- newCurL = curL;
- newCurR = curR + (curR - curL) + 1;
- }
- else
- { //distance son он всегда четный
- int edge = (tree[curL - 1].color && tree[curL].color) ? -1 : 0; // Если границы с соседним отрезком черные, то кол-во отрезков = их сумме минус 1
- tree[getParentNode(node)].countBlackSegment = tree[node].countBlackSegment +
- tree[node - 1].countBlackSegment + edge;
- // Ставим длинну для родителя(просто сумма детей)
- tree[getParentNode(node)].lengthBlack = tree[node - 1].lengthBlack +
- tree[node].lengthBlack;
- newCurL = curL - (curR - curL) - 1;
- newCurR = curR;
- }
- //push up теперь переходим в родителя
- pushUp(getParentNode(node), newCurL, newCurR);
- }
- // ну это просто обновление детей детей(протоклнули) (тут node - это нода одного из детей)
- void propogate(int node, int curL, int curR, bool color)
- {
- tree[node].upAndWeCorrectDownNo = true;
- tree[curL].color = color;
- tree[curR].color = color;
- tree[node].color = color;
- if (color)
- {
- tree[node].lengthBlack = (curR - curL) + 1;
- tree[node].countBlackSegment = 1;
- }
- else
- {
- tree[node].lengthBlack = 0;
- tree[node].countBlackSegment = 0;
- }
- }
- void createTree()
- {
- tree.resize(SIZE);
- }
- int getParentNode(int node)
- {
- int delta = SIZE - 1 - node;
- return SIZE - 1 - (delta - 1) / 2;
- }
- int leftChildren(int node)
- {
- int delta = SIZE - 1 - node;
- return SIZE - 1 - (delta + 1) * 2;
- }
- int rightChildren(int node)
- {
- int delta = SIZE - 1 - node;
- return SIZE - 1 - (delta) * 2 - 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement