Изменения
Нет описания правки
# То же, что и в предыдущем задании, но для каждого фиксированного $i$ надо научиться получать строку с нуля за $O(|s|)$.
# Тандемный повтор - строка вида $a = bb$. Найти максимальный тандемный повтор за $O(n \log n)$, используя результат предыдущего задания. Указание: используйте алгоритм вида "разделяй и властвуй", разделите строку пополам, ответ либо лежит слева от точки деления, либо справа, либо пересекает ее.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес максимальное ребро на пути из $u$ в $v$". Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос). # Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано взвешенное дерево. Разбить вершины его на множество путей (каждая вершина принадлежит ровно одному пути), чтобы путь от любой вершины до любой переходил с одного пути на другой не более $O(\log n)$ раз.
# Дано взвешенное дерево. Уметь отвечать на запросы "минимальное ребро на пути из $u$ в $v$" и "изменить весь ребра $uv$" за полином от логарифма.
# Дано взвешенное дерево. Научиться Уметь отвечать на запросы "максимальное ребро сумма ребер на пути из $u$ в $v$" и "изменить весь ребра $uv$" за $O(\log n^2)$.
# Дан массив $a$. Посчитать массив $RMQ[i][j] = min(a[i] ... a[j])$ за $O(n^2)$.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d) $ памяти для каждой маски.# Свести задачу RMQ к задаче LCA линейного размера (указание: использовать декартово дерево)
</wikitex>
