Изменения
Нет описания правки
# Дано $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$-й элемент массива.
</wikitex>
