Сборы к РОИ, группа A1 (16 марта 2016)

  1. Dynamic Connectivity Offline
    1. Корневая по запросам за O(n3/2)
    2. Разделяй и властвуй по запросам, СНМ с откатами за O(nlog2n)
    3. Разделяй и властвуй по запросам, сжатие компонент за O(nlogn)
  2. Задачи на корневую по запросам
    1. Add(x,y); Get(x,y); Count(x1,x2,y1,y2) за O((nlogn)1/2 + log2n) на запрос
    2. Ахо-Корасик: build(dictionary), add(word), del(word), get(text)
    3. Dynamic MST Offline за O(n3/2α)
  3. Разбор
    1. A: Разделяй и властвуй на запросах
    2. B: Корневая по запросам, внутри выпуклая оболочка и бинпоиск
    3. C: Heavy-Light-Decomposition, или спомощью LCA соседних получить новое маленькое дерево
    4. D: двоичные поъёмы, бинпоиск, сумма на поддереве
    5. E: поиск отрицательного цикла Форд-Беллманом