Dynamic-Connectivity Online
=====

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

* Все запросы в online
* Добавление ребра за $O(log^2n)$
* Удаление ребра за $O(log^2n)$
* Проверка, лежат ли две вершины в одной компоненте связности за $O(logn)$

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

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

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

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

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

* Храним для каждого ребра две ориентированных копии, для каждой вершины одну копию.<br>Построение: обойдём дерево, вершину выписываем при входе в неё, ребро при проходе по нему.
* Поддерживаем размер поддеревьев. Умеем делать split и merge.
* Умеем от вершины декартова дерева подняться до корня (храним родителей).
* Для каждого ребра знаем 2 вершины в каждом из $log_{2}n$ treap. Для каждой вершины знаем 1 вершину в каждом из $log_{2}n$ 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 + log_2n)$. Так же мы для t из перебранных рёбер увеличим ранг.<br>Благодаря амортизации в сумме по всем запросом мы переберём не более $m + nlog_{2}n$ рёбер.
* Перебор рёбер нужного ранга: в treap кроме всего прочего мы храним количество вершин в поддереве,<br>которым соответствует вершина исходного графа, из которой есть исходящие рёбра нужного ранга.
