e-olymp 8379. Нулі та одиниці

Задача взята с сайта 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$ до $5.$ Це завдання будемо вирішувати за допомогою персистентного дерева відрізків. Зміст персистентного дерева відрізків в тому, що воно зберігає всі попередні версії самого дерева, тобто всі його стани після будь-яких модифікацій. Суть в тому, що коли ми спускаємося по дереву ми всього лише пройдемо максимум по $\log (n)$ його вершинах, що дає нам при запиті на модифікацію можливість не просто «тупо» скопіювати весь масив з $4 \cdot n$ елементів, а зберегти нову версію дерева, де зміняться лише $\log (n)$ вершин. Тобто сумарно $k \cdot \log (n)$ пам’яті замість $k \cdot n.$ Побудова персистентного дерева відрізків буде аналогічно побудові звичайного дерева відрізків за винятком того, що тепер для кожної вершини додатково доведеться в явному вигляді зберігати посилання на дочірні вершини. Додатково будемо зберігати вектор вершин, що є корінням у відповідних версіях дерева. При будові, в нього додамо єдину вершину, що є коренем отриманого дерева. Таким чином, складність побудови залишилася незмінною, а саме $O(n).$  При зміні вершини до нього будуть додані тільки ті вершини, які повинні були змінитися, і замість зміни значень старих вершин, перераховані значення будуть збережені в нові. Всі нові вершини будуть посилатися на одну вершину з дерева старої версії і на одну з щойно доданих. Тим самим, при запиті оновлення буде створено $O (\log (n))$ нових вершин, у тому числі буде створено новий корінь дерева відрізків, а вся попередня версія дерева, підвішена за старий корінь, залишиться без змін. Наприкінці потрібно зазанчити, що задача заходить на eolymp за часом лише з використанням функцій вводу/виводу scanf() та printf().

Посилання

ideone

e-olymp

Дерево відрізків на e-maxx

e-olymp 2955. Персистентый массив

Условие

Задача взята отсюда.

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

  • [latex]a_i[j] = x[/latex] — создать из [latex]i[/latex]-ой версии новую, в которой [latex]j[/latex]-ый элемент равен [latex]x[/latex], а остальные элементы такие же, как в [latex]i[/latex]-ой версии.
  • [latex]get[/latex] [latex]a_i[j][/latex] — сказать, чему равен [latex]j[/latex]-ый элемент в [latex]i[/latex]-ой версии.

Входные данные

Количество чисел в массиве [latex]n[/latex] [latex](1 \leq n \leq 10^5)[/latex] и [latex]n[/latex] элементов массива. Далее количество запросов [latex]m[/latex] [latex](1 \leq m \leq 10^5)[/latex] и [latex]m[/latex] запросов. Формат описания запросов можно посмотреть в примере. Если уже существует [latex]k[/latex] версий, новая версия получает номер [latex]k + 1[/latex]. И исходные, и новые элементы массива — целые числа от [latex]0[/latex] до [latex]10^9[/latex]. Элементы в массиве нумеруются числами от [latex]1[/latex] до [latex]n[/latex].

Выходные данные

На каждый запрос типа [latex]get[/latex] вывести соответствующий элемент нужного массива.

Тесты

Входные данные выходные данные
1 6
1 2 3 4 5 6
11
create 1 6 10
create 2 5 8
create 1 5 30
get 1 6
get 1 5
get 2 6
get 2 5
get 3 6
get 3 5
get 4 6
get 4 5
6
5
10
5
10
8
6
30
2 2
42 2048
17
create 1 1 1
create 2 2 1
create 3 2 5
create 3 1 4
create 5 2 6
get 1 1
get 1 2
get 2 1
get 2 2
get 3 1
get 3 2
get 4 1
get 4 2
get 5 1
get 5 2
get 6 1
get 6 2
42
2048
1
2048
1
1
1
5
4
1
4
6

Код

Решение

Для решения задачи воспользуемся так называемым Персистентным Деревом Отрезков — т.е. деревом, «помнящим» историю своих изменений. Дерево будем хранить не с помощью массива а на указателях — используя структуру типа «узел».

(Тут [latex]lchild[/latex] и [latex]rchild[/latex] — ссылки на левый и правый поддеревья соответственно, а [latex]val[/latex] — значение, хранящееся в узле.)

Замечание: тут и далее под левым подотрезком отрезка [latex][l, l + 1, \ldots, m, m + 1, \ldots, r — 1, r][/latex], [latex]m = \lfloor\frac{l + r}{2}\rfloor[/latex] подразумевается отрезок [latex][l, \ldots, m][/latex] а под правым — [latex][m + 1, \ldots, r][/latex].

Заведем вектор-хранилище корней дерева [latex]versions[/latex] (об этом позднее). Для начала занесем туда 1 элемент — корень изначального дерева, и построим на нем дерево из элементов массива. Вопрос в том, какую информацию хранить в вершинах дерева? Оказывается, достаточно хранить в листьях элементы массива, а остальные узлы заполнять ни чем не надо — исходя из условия, запросы будут только к конкретным элементам массива. Рекурсивная процедура построения дерева стандартна, отличается только технической реализацией (вместо номеров вершин передаем ссылки на необходимые нам узлы) — рекурсивно создаем у текущего узла [latex]lchild[/latex] и [latex]rchild[/latex] и вызываем функцию построения для них, пока длина отрезка, за который они отвечают, не станет равна единице. Тогда присваиваем полю [latex]val[/latex] этого узла значение соотв. элемента массива.

Например, для массива {[latex]1, 2, 3, 4, 5, 6[/latex]} в результате построения мы получим следующую структуру (где на самом деле значения хранятся только на отрезках длины [latex]1[/latex], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).
graph1
Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [latex]k[/latex] версий массива и мы хотим создать из [latex]i[/latex]-й [latex](k+1)[/latex]-ю. Для начала добавим в хранилище новый узел-корень, отвечающий данной версии.

Теперь рассуждаем так: допустим, элемент, который надо поменять, находиться в правом подотрезке (для левого, рассуждения будут симметричны). Левые подотрезки идентичны, тогда просто присваиваем [latex]lchild[/latex] нового узла ссылку на [latex]lchild[/latex] исходного. Правые будут отличаться. Тогда создаем у нового узла [latex]rchild[/latex], и проводим те же размышления относительного правого подотрезка, [latex]rchild[/latex]-ов исходного и нового узлов, повторяя это до тех пор, пока мы не придем в лист дерева, тогда просто присвоим этому новому узлу требуемое значение. Получаем несложный рекурсивный алгоритм функции void add(Node* to, Node* from, int l, int r, int npos, int nv);

Для наглядности, рассмотрим пример с тем же массивом. Пусть сперва нас просят выполнить create 1 6 42 — создать из первой версии новую, где шестой элемент равен [latex]42[/latex], а затем create 2 4 667 — создать новую уже из второй, где [latex]4[/latex]-й элемент равен [latex]667[/latex]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

graph2

Рассмотрим, как получилась вторая версия. Создаем корень {[latex]1, 2, 3, 4, 5, 42[/latex]}. Необходимый нам элемент в правом подотрезке. Тогда [latex]lchild[/latex] нового корня будет ссылаться на [latex]lchild[/latex] исходного, а [latex]rchild[/latex] {[latex]4, 5, 42[/latex]}. Мы создаем. Аналогично поступаем с {[latex]4, 5, 42[/latex]} относительно {[latex]4, 5, 6[/latex]}. Левое поддерево {[latex]4, 5[/latex]} — общее, создаем правое поддерево {[latex]42[/latex]} и завершаем алгоритм. Для получения третьей версии можно провести аналогичные рассуждения, но уже беря в качестве исходного дерева вторую версию.

Так как на каждом этапе отрезок делится пополам, то очевидно, что как и в стандартной реализации ДО, асимптотика этой функции будет [latex]O(\log{n})[/latex], а при создании новой версии будет создано не более чем [latex]\lceil\log_2{n}\rceil[/latex] вершин, т.е. алгоритм является достаточно эффективным как в плане времени, так и расходуемой памяти.

Осталось реализовать функцию int get(Node* node, int l, int r, int pos);
Она реализуется стандартно: спускаемся по необходимой версии дерева (из нужного узла-корня в [latex]storage[/latex]), в левое или правое поддерево, пока не дойдем до необходимой нам вершины (это будет отрезок единичной длины), далее возвращаем содержимое [latex]val[/latex] этого узла. Реализация облегчается еще и тем, что запрашивают элемент — т.е. отрезок единичной длины, и не надо рассматривать случай, когда необходимый отрезок лежит частично в левом, а частично в правом поддереве.

Таким образом, мы получили структуру, выполняющую поставленную задачу с эффективной асимптотикой по времени и памяти. В главной функции просто считываем изначальный массив, заводим вектор, заносим в него первый узел и строим из него дерево по считанному массиву. Затем в цикле в зависимости от запроса вызываем необходимую функцию.

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на Ideone.

Замечание

Легко заметить, что в функции int get(Node* node, int l, int r, int pos); можно очень просто избавиться от рекурсии:

Но, судя по результатам, это в принципе не влияет на скорость работы программы.