Изменения
Нет описания правки
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
# Предложите алгоритм с временем работы $O(n)$ для следующей задачи: задан массив из неотрицательных чисел и число $k$, определите число отрезков с суммой, не превышающей $k$. Также проанализируйте, работает ли ваш алгоритм, если массив может содержать отрицательные числа: постройте контрпример или докажите, что работает.
# Запросы на статическом массиве: задано число $k$ и запросы~{{--- отрезки }} посчитать ассоциативную необратимую функцию на отрезке длины от $k$ до $2k$. Ответ на запросы за $O(1)$ и препроцессинг за $O(n)$.# Запросы: 1. set(i, x) {{---}} $a[i] a_i := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y a_i \ge s$, $\sum\limits_{i=1}^{y - 1} a_i < s$ за $O(\log{n})$. # Обработайте $Qq$ запросов на прибавление на отрезке, получите конечный массивдлины $n$, за $O(Qn + q)$.
# Обработайте запросы за $O(\log{n})$. Первый {{---}} присвоить значение элементу, второй {{---}} задан отрезок, найти подотрезок с максимальной суммой, содержащийся в этом отрезке.
# Сведите задачу к запросам изменения в точке и функции на отрезке за $O(\log{n})$. Задача {{---}} отвечать на запросы: прибавление на отрезке и минимум на отрезке.
# Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке. Время работы $o(n)$ на запрос (это задача-аукцион, пишите свое среднее время работы на запрос, время предпосчета и памяти на заявке)
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке. Время на запрос $O(\log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке. Время работы $o(n)$ на запрос (это задача-аукцион, пишите свое среднее время работы на запрос, время предпосчета и памяти на заявке)
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти площадь объединения прямоугольников за $O(n \log n)$.
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.
# Решите за $O(\sqrt{n}\log{n})$ на запрос амортизированно. Поступают запросы: развернуть отрезок и посчитать количество элементов на отрезке от $x$ до $y$.
# Решите предыдущую задачу за $O(\sqrt{n\log{n}})$ на запрос истинно.
# Решите с помощью персистентного дерева отрезков. Дано $n$ точек. Поступают запросы в online: прямоугольник со сторонами, параллельными осям координат, нужно найти $k$-ю точку по возрастанию $y$-координаты, среди лежащих внутри этого прямоугольника. Время работы: $O(\log{n})$ на запрос.
# Решите предыдущую задачу без персистентного дерева отрезков.
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число и вывести сумму сумм всех подотрезков отрезка.
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число, умножить все элементы на отрезке на заданное число, вывести $i$-й элемент массива.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(K \log{K})$ бит памяти для каждой маски.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$" и "изменить вес ребра". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес ребра" и "прибавить ко всем ребрам на пути от $v$ до $u$ число $d$". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Алгоритм Хьюи. Дано дерево, вершины которого раскрашены в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы: $O(V)$.
# Задано взвешенное дерево. Посчитать число простых путей в дереве длины от $L$ до $R$ и весом от $x$ до $y$. Время работы $O(n \log^2{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, покрасить черную вершину в белую, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log^2{n})$.
# Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$
# Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.
# Рассмотрим подвешенное дерево. Пусть $s(v)$ {{---}} размер поддерева с корнем в вершине $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $h(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} s(u)$, $f(v) = s(v) - s(h(v))$. Доказать, что $\sum\limits_{v \in V}f(v) = O(n \log{n})$.
# Рассмотрим подвешенное дерево. Пусть $k(v)$ {{---}} высота поддерева с корнем $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $d(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} k(u)$, $g(v) = \sum\limits_{\substack{
u \in C(v) \\
u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
# Задано подвешенное дерево. Нужно отвечать на запросы: подвесить вершину как лист к одной из имеющихся вершин, найти наименьшего общего предка двух уже добавленных вершин. Время работы запросов: $O(n \log{n})$.
# Предложите алгоритм добавления в АВЛ-дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из АВЛ-дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм добавления в красно-черное дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из красно-черного дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
# Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
# В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
# Докажите, что высота красно-черного дерева $O(\log{n})$.
</wikitex>
