Структуры данных: lower bounds

  1. Сортировка: NlogN
  2. Heap: extractmin = logN
  3. Дерево отрезков: max(change,query) = logN
  4. Выпуклая оболочка: NlogN

Структуры данных

  1. Меняющееся дерево
    1. Сумма на пути дерева = LCA + дерево отрезков.
    2. Минимум на пути дерева = 2D-запрос
  2. Not read Прямоугольные запросы
    1. Not read Сумма на прямоугольнике за O(1)
    2. Not read Минимум на прямоугольнике за O(1)
    3. Not read Иначе 2D-дерево отрезков или дерево Фенвика
  3. Запросы на N точках
    1. Простая задача "permutations" (напоминание). Простая ее реализация.
    2. Произвольные N точек → permutations
    3. КД-дерево
    4. Not read Специальное 2D дерево, отвечающее на 1 запрос за O(logN).
  4. Heavy-Light decomposition (покрытие дерева путями)
  5. Linking-Cutting trees
    1. Покрытие дерева декартовыми деревьями по неявному ключу.
    2. Expose
    3. MakeRoot
    4. Get, Link, Cut

Задачи (2-я серия)

  1. Not read [matching] Дан произвольный двудольный граф, нужно разбить его на минимальное кол-во паросочетаний.
  2. Not read [cover] Удаление графа
  3. Not read [cut] Задача про заказы и инструменты
  4. Not read [matching] Такси
  5. Not read [matching] Задача с РОИ
  6. Not read [matching, independent set] Антицепь, теорема Дилворта

Разрезы

  1. Not read Глобальный разрез. Нахождение за O(N3) (алгоритм Штор-Вагнера без док-ва).

MinCost потоки

  1. Not read Венгерский алгоритм.
  2. Not read Реализация венгерки за O(N3)