9
правок
Изменения
Нет описания правки
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Предложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Предложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.h
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "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] := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y \ge s$, $\sum\limits_{i=1}^{y - 1} < s$ за $O(\log{n})$.
# Обработайте $Q$ запросов на прибавление на отрезке, получите конечный массив, за $O(Q)$.
# Обработайте запросы за $O(\log{n})$. Первый {{---}} присвоить значение элементу, второй {{---}} задан отрезок, найти подотрезок с максимальной суммой, содержащийся в этом отрезке.
# Сведите задачу к запросам изменения в точке и функции на отрезке за $O(\log{n})$. Задача {{---}} отвечать на запросы: прибавление на отрезке и минимум на отрезке.
# Решите за $O(\log{n})$ на запрос. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ непересекающихся отрезков из выбранного множества
# Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
</wikitex>
