Czy ktoś kto zrobił OSA, albo ma jakieś sensowne pomysły, mógłby się nimi podzielić?

Miałam jakiś zarys rozwiązania bazujący na tym: https://en.wikipedia.org/wiki/Dynamic_connectivity#General_graphs ale brakło mi czasu nawet na dokończenie pomysłu, nie mówiąc już o implementacji. Więc nie wiem nawet czy to dobra droga.

My solution is to maintain the dual graph, so all cut operation becomes link operations in the dual graph.
And the only thing we need to check is if all the 'K's are inside/outside the circle when we try to link a circle in the dual graph.
For each 'K' we can give it a random value w[k] and shoot a ray to the right. Then let the value of a edge of the dual graph be the XOR sum of all rays intersect it. So the only thing we need to check is if the XOR sum of the value of the edges in the circle is equal to 0 or the XOR sum of all points. It can be maintained by using union-find sets.
And if the 'K' moves, we can twist the beginning of the ray and remain the right part unchanged. So there is only one unlinked edge changed its value in the dual graph per move.

Korzystam z tego, że sytuacja się dzieje na planszy (a nie na dowolnym grafie). Generalnie pomysł mi przyszedł z metody liczenia pola wielokąta metodą trapezów - zamiast pola liczę tak ilości osad i w ten sposób będę sprawdzał czy jakieś osady zostały odgrodzone.

Utrzymuje spójne fragmenty warowni na planszy w postaci ich dowolnych drzew rozpinających, dla każdego wybieram dowolnie korzeń. Dla każdego pola/wierzchołka w takim drzewie trzymam "skierowaną" sumę ilości osad pod ścieżką (dosłownie pod polami na planszy) od korzenia do danego węzła (przez skierowaną rozumiem że dodaję gdy krawędź prowadzi do pola na lewo, bądź odejmuję gdy na prawo). W momencie dołożenia warowni, gdy łączy ona 2 różne drzewa to podłączam mniejsze do większego i przeliczam wartości na nowo. Natomiast gdy łączy 2 elementy z jednego drzewa to powstaje cykl - wtedy używam wyliczonych sum dla wierzchołków, które łączy nowa warownia by wyliczyć ile osad leży w środku i odrzucam zapytanie jeśli potrzeba. A gdy zaakceptujemy zapytanie (w cyklu nie było osad albo były wszystkie) no to merguję tę warownię z drzewem (cyklu nie robię, trzymam drzewo rozpinające).

edit: A no i do przesuwania osad trzymam sobie dla każdej kolumny wartości w drzewach Fenwicka o ile trzeba poprawiać sumy.