Задача взята с сайта e-olymp.
Задача
Їжачок Аліна, переглядаючи свої старі зошити знайшла в одному з них неймовірно цікавий масив з нулів. Виявилось, що Аліна з цим масивом вміє робити кілька неймовірно цікавих операцій:
- Присвоїти елементу в позиції $x$ значення $1.$
- Присвоїти елементу в позиції $x$ значення $0.$
- Замінити на відрізку від $l$ до $r$ всі нулі на одиниці і навпаки.
- Повернути масив в стан, який був після $x$-ої операції.
- Знайти кількість одиниць на підвідрізку масиву від $l$ до $r.$
Вхідні дані
В першому рядку задано два натуральні числа $N \leqslant 10^5$ i $M \leqslant 2 \cdot 10^5,$ що позначають розмір масива і кількість операцій відповідно. В наступних $M$ рядках задано інформацію про операції.
Вихідні дані
Для кожної операції типу $5$ вивести кількість одиниць на підвідрізку від $l$ до $r.$
Тести
| # | Входные данные | Выходные данные |
|
1 |
8 7 1 1 3 1 4 5 1 5 2 3 5 1 5 4 1 5 1 5 |
3 2 1 |
|
2 |
4 5 1 2 1 3 2 2 3 1 3 5 1 2 |
2 |
|
3 |
4 7 1 2 1 3 2 2 3 1 3 5 1 2 4 1 5 1 2 |
2 1 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <iostream> #include <vector> using namespace std; struct node { int value = 0; node * right, * left; int l, r; int unPushed = 0; node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { } node * clone() { node * ans = new node(l, r); ans -> right = right; ans -> left = left; ans -> value = value; ans -> unPushed = unPushed; return ans; } }; vector<node *> v; int sum(node * left, node * right) { int ans = 0; if(left != nullptr) ans += left -> value; if(right != nullptr) ans += right -> value; return ans; } void push(node *(&k)) { k -> unPushed %= 2; if (k -> unPushed) { int center = (k -> l + k -> r) / 2; if (k -> left == nullptr) k -> left = new node(k -> l, center); else k -> left = k -> left -> clone(); if (k -> right == nullptr) k -> right = new node(center + 1, k -> r); else k -> right = k -> right -> clone(); ++k -> left -> unPushed; ++k -> right -> unPushed; k -> left -> value = (center - k -> l + 1) - k -> left -> value; k -> right -> value = (k -> r - center) - k -> right -> value; k -> unPushed = 0; } } void updateSegment(node *(&k), int left, int right, int l, int r) { if(k == nullptr) k = new node(left, right); else k = k -> clone(); if(l > r) return; if(l == left && r == right) { ++k -> unPushed; k -> value = (r - l + 1) - k -> value; return; } int center = (left + right) / 2; push(k); updateSegment(k -> left, left, center, l, min(r, center)); updateSegment(k -> right, center + 1, right, max(l, center + 1), r); push(k -> left); push(k -> right); k -> value = sum(k -> left, k -> right); } void update(node *&k, int left, int right, int pos, int a) { if (k == nullptr) k = new node(left, right); else k = k -> clone(); if (left == right) { k -> value = a; return; } int center = (left + right) / 2; push(k); if(pos <= center) { update(k -> left, left, center, pos, a); push(k -> left); } else { update(k -> right, center + 1, right, pos, a); push(k -> right); } k -> value = sum (k -> left, k -> right); } int query(node *k, int left, int right, int l, int r) { if (l > r) return 0; if(k == nullptr) return 0; if(left == l && r == right) return k -> value; int center = (left + right) / 2; push(k); return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r); } int main() { int n, m, type, pos, l, r; scanf("%d %d", &n, &m); v.push_back(new node(1, n)); for(int i = 1; i <= m; i++) { scanf("%d", &type); if(type <= 2) { scanf("%d", &pos); type = 2 - type; v.push_back(v.back() -> clone()); int k = query(v.back(), 1, n, pos, pos); if(k != type) updateSegment(v.back(), 1, n, pos, pos); } else if(type == 3) { scanf("%d %d", &l, &r); v.push_back(v.back() -> clone()); updateSegment(v.back(), 1, n, l, r); } else if(type == 4) { scanf("%d", &pos); v.push_back(v[pos] -> clone()); } else if(type == 5) { scanf("%d %d", &l, &r); v.push_back(v.back() -> clone()); printf("%d\n", query(v.back(), 1, n, l, r)); } } return 0; } |
Рішення
Спочатку потрібно декілька з’ясувати умову завдання, адже в ній не сказано за що відповідає перше число в кожному запиті. Це число — це номер операції, які задані в умові задачі, вони нумеруються від $1$ до $5.$ Це завдання будемо вирішувати за допомогою персистентного дерева відрізків. Зміст персистентного дерева відрізків в тому, що воно зберігає всі попередні версії самого дерева, тобто всі його стани після будь-яких модифікацій. Суть в тому, що коли ми спускаємося по дереву ми всього лише пройдемо максимум по $\log (n)$ його вершинах, що дає нам при запиті на модифікацію можливість не просто «тупо» скопіювати весь масив з $4 \cdot n$ елементів, а зберегти нову версію дерева, де зміняться лише $\log (n)$ вершин. Тобто сумарно $k \cdot \log (n)$ пам’яті замість $k \cdot n.$ Побудова персистентного дерева відрізків буде аналогічно побудові звичайного дерева відрізків за винятком того, що тепер для кожної вершини додатково доведеться в явному вигляді зберігати посилання на дочірні вершини. Додатково будемо зберігати вектор вершин, що є корінням у відповідних версіях дерева. При будові, в нього додамо єдину вершину, що є коренем отриманого дерева. Таким чином, складність побудови залишилася незмінною, а саме $O(n).$ При зміні вершини до нього будуть додані тільки ті вершини, які повинні були змінитися, і замість зміни значень старих вершин, перераховані значення будуть збережені в нові. Всі нові вершини будуть посилатися на одну вершину з дерева старої версії і на одну з щойно доданих. Тим самим, при запиті оновлення буде створено $O (\log (n))$ нових вершин, у тому числі буде створено новий корінь дерева відрізків, а вся попередня версія дерева, підвішена за старий корінь, залишиться без змін. Наприкінці потрібно зазанчити, що задача заходить на eolymp за часом лише з використанням функцій вводу/виводу scanf() та printf().