Заголовок.

# Dynamic-Connectivity Online

## Что мы хотим получить?

- Все запросы в online
- Добавление ребра за O(log2n)
- Удаление ребра за O(log2n)
- Проверка, лежат ли две вершины в одной компоненте связности за O(logn)

## Наивные решения

- Add = O(1), Del = O(1), Get = O(m)
- Add = DSU, Del = O(n+m), Get = DSU

## Конструкция для правильного решения

- У каждого ребра есть ранг от 0 до log2n. При добавлении равен 0.
- Для каждого k = 0..log2n мы поддерживаем ET[k] − остовный лес на рёбрах с рангом 0..k
- В ET[k] размер каждой компоненты связности не более n / 2k. ET[0] − остов всего графа.
- Если ребро присутствует в остове ET[k], то оно присутствует и в ET[0]..ET[k-1].
- В ET[k] мы храним как Эйлеровы Обходы деревьев.

## Хранение Эйлеровых обходов

- Храним для каждого ребра две ориентированных копии, для каждой вершины одну копию.
  Построение: обойдём дерево, вершину выписываем при входе в неё, ребро при проходе по нему.
- Поддерживаем размер поддеревьев. Умеем делать split и merge.
- Умеем от вершины декартова дерева подняться до корня (храним родителей).
- Для каждого ребра знаем 2 вершины в каждом из log2n treap. Для каждой вершины знаем 1 вершину в каждом из log2n treap. Если такой вершины нет, храним 0.

## Обработка запросов

- База: на каждом уровне каждая вершина лежит в своём декартовом дереве, состоящим только из этой вершины. Рёбер нет.
- Ответ на запрос `get(a, b)`: `getRoot(vertexPosition[a, 0]) == getRoot(vertexPosition[b, 0])`
- Запрос `add(a, b)`: `if (!get(a, b)) { новое ребро = {a, b, rank=0}; makeRoot(a); makeRoot(b); merge(getRoot(a), новое ребро, getRoot(b), новое ребро) }`
- Запрос `del(a, b)`: `i = индекс ребра; if (edgePosition[i, rank[i]] == 0) return; for (j=0..rank[i]) { ET[j].splitByEdge(i); } найти замену!`

## Поиск ребра-замены-старого

- Ребро (a,b) ранга k разбило дерево на две компоненты. Возьмём из них за O(1) меньшую (мы знаем размер каждой).
- В меньшей из них все внутренние рёбра ранга k можно сделать ранга k+1
- И нужно найти хотя бы одно ребро наружу ранга не более k.
- Для этого научимся в ET[k] перебирать все рёбра ранга ровно k. И применим это к ET[j] в порядке j=k..0, пока не найдём ребро-замену-старому.
- В итоге мы переберём t + 1 ребро за время O(t+log2n). Так же мы для t из перебранных рёбер увеличим ранг.
  Благодаря амортизации в сумме по всем запросом мы переберём не более m+nlog2n рёбер.
- Перебор рёбер нужного ранга: в treap кроме всего прочего мы храним количество вершин в поддереве,
  которым соответствует вершина исходного графа, из которой есть исходящие рёбра нужного ранга.