Napój Wielkiej Potęgi

Po otrzymaniu informacji o wszystkich modyfikacjach, należy odpowiadać online na $q\le 5\cdot {10}^4$ zapytań, każde opisane parą wierzchołków $x,y$ oraz momentem $0\le v\le U$. Odpowiedź na zapytanie to najmniejsza różnica $|h_a-h_b|$, gdzie $a$ jest sąsiadem $x$ oraz $b$ jest sąsiadem $y$ w momencie $v$.

Podzadanie 2

Dla $q,U\le {10}^3$ wystarczy dla każdego zapytania zaaplikować na grafie wszystkie modyfikacje grafu do danego momentu $v$, a następnie przeiterować się po każdym sąsiedzie $x$ oraz $y$. Daje to algorytm o złożoności czasowej $O(qUD+q{D}^2)$ lub $O(qU\log (D)+q{D}^2)$, zależnie od sposobu przechowywania grafu (za pomocą typów jak set można usuwać elementy w złożoności $O(\log D)$).

Zamiast iterować się po każdej parze sąsiadów w $O(q{D}^2)$, można najpierw posortować sąsiadów według ich wysokości, a potem gąsienicą dla kolejnych sąsiadów $x$ utrzymywać sąsiada $y$ o najmniejszej wyższej wysokości (albo alternatywnie znajdywać takiego sąsiada $y$ za pomocą wyszukiwania binarnego), co daje złożoność $O(qD\log (D))$. W tym podzadaniu takie podejście nie było potrzebne, ale przyda się w kolejnych podzadaniach.

Podzadanie 5 -- rozwiązanie ze spamiętywaniem co pierwiastek

W tym podzadaniu zachodzi $n,U\le {10}^4$.

Co $\sqrt{U}$ modyfikacji można zapisać aktualny graf, dzięki czemu, mając zapytanie w momencie $v$, zamiast budować cały graf od nowa, można znaleźć najbliższą wcześniejszą zapisaną modyfikację (która jest odległa o co najwyżej $\frac{U}{\sqrt{U}}=\sqrt{U}$ modyfikacji) i zaaplikować na niej późniejsze modyfikacje, aby otrzymać graf w momencie $v$. Daje to rozwiązanie o złożoności $O(U\log (D)+U\sqrt{U}+q(\sqrt{U}+D)\log (D))$ oraz pamięci $O(U\sqrt{U})$.

Podzadanie 5 -- rozwiązanie z trzymaniem sąsiadów tylko po aktualizacji

Jeżeli w momencie $v$ modyfikacja krawędzi nie dotyczyła wierzchołka $x$, to lista jego sąsiadów jest taka sama, co w momencie $v-1$. Można dla każdej modyfikacji dotyczącej wierzchołka $x$ zapisać sobie jego listę sąsiadów po tej modyfikacji, a następnie dla danego zapytania znaleźć ostatnią aktualną listę sąsiadów (na przykład wyszukiwaniem binarnym) i na niej wyszukać odpowiedź. Łącznie nie będzie więcej niż $2U$ kopii listy sąsiadów (jest to zsumowana liczba list po wszystkich wierzchołkach), a każda lista sąsiadów jest rozmiaru co najwyżej $D$. Daje to rozwiązanie o złożoności $O(UD+q(D+\log (U)))$ oraz pamięci $O(UD)$.

Podzadanie 5 -- rozwiązanie z drzewami trwałymi

Można skorzystać z trwałych zrównoważonych drzew wyszukiwań binarnych lub trwałych drzew przedziałowych, aby utrzymać dla każdego momentu listę sąsiadów wszystkich wierzchołków. Takie rozwiązania zazwyczaj nie otrzymywały 100 punktów przez zbyt dużą złożoność lub stałą, zarówno czasową, jak i pamięciową (struktury trwałe wymagają dodatkowego czynnika $O(\log (n))$ w pamięci).

Podzadanie 5 -- rozwiązanie z drzewem przedziałowym po czasie

Każda krawędź jest w grafie w momentach będącą sumą rozłącznych przedziałów. Wszystkich takich przedziałów jest co najwyżej $U$.

Można stworzyć drzewo przedziałowe (analogiczne do opisanego w tym artykule). Takie drzewo ma co najmniej $U$ liści i dla każdego przedziału $[l,r]$ istnienia pewnej krawędzi $e$, rozbija się ten przedział na wierzchołki bazowe i do nich (na przykład do set-a) wrzuca się krawędź $e$. Wtedy jest spełniony warunek, że dla każdego momentu, set wszystkich krawędzi grafu w tym momencie to dokładnie złączenie setów krawędzi na ścieżce od odpowiedniego liścia do korzenia drzewa przedziałowego. Stworzenie takiego drzewa ma złożoność $O(U{\log }^2(U))$ czasową i $O(U\log (U))$ pamięciową, ponieważ każda krawędź może wystąpić w $O(\log (U))$ wierzchołkach bazowych.

Aby otrzymać listę sąsiadów $x$ dla danego momentu $v$, można dla każdego wierzchołka na ścieżce od $v$-tego liścia do korzenia wyszukać w tych set-ach krawędzie o takim wierzchołku i złączyć takie listy krawędzi w jedną. Dlatego złożoność czasowa rozwiązania wynosi $O((U+q){\log }^2(U)+qD\log (D))$.

Pełne zadanie -- zapisanie listy krawędzi co ileś modyfikacji

Żeby rozwiązać zadanie na pełnych limitach, można połączyć rozwiązanie ze spamiętywaniem co pierwiastek z rozwiązaniem z trzymaniem sąsiadów tylko po aktualizacji.

Można zapisać listę sąsiadów danego wierzchołka $x$ co $C$ modyfikacji listy sąsiadów tego wierzchołka, dla pewnej wybranej stałej $C$. Dodatkowo też trzeba zapisać uporządkowaną listę zmian każdego wierzchołka. Wtedy, by otrzymać listę sąsiadów wierzchołka $x$ w momencie $v$, trzeba znaleźć (na przykład wyszukiwaniem binarnym) ostatnią zapisaną listę i ręcznie dodać co najwyżej $C$ krawędzi do tej listy sąsiadów.

Stałą $C$ należy tak dobrać, aby jak najbardziej zmniejszyć czas działania programu, ale tak, aby wciąż zmieścić się w limitach pamięci. Można na przykład wybrać $C=50$.

Złożoność czasowa wynosi $O(U\log (D)+\frac{UD}{C}+q(D+\log (U)+C\log (D))$ oraz pamięciowa wynosi $O(\frac{UD}{C})$.

Pełne zadanie -- wiele drzew przedziałowych po czasie

Można wykonać optymalizację rozwiązania z drzewem przedziałowym po czasie, aby działała na pełnych limitach.

Zamiast wyszukiwać binarnie odpowiednią listę krawędzi wśród set'ów wierzchołków na ścieżce od liścia do korzeni, można stworzyć drzewo przedziałowe po czasie oddzielnie dla każdego wierzchołka $x$, co eliminuje to wyszukiwanie binarne.

Ponieważ nie można utrzymywać takiego pełnego drzewa binarnego o $U$ liściach dla każdego wierzchołka $x$, to trzeba utrzymywać te drzewa przedziałowe w skompresowanej formie (czyli ma to być drzewo wskaźnikowe lub drzewo przedziałowe skonstruowane offline).

Daje to rozwiązanie o złożoności czasowej $O((U+q)\log (U)+qD\log (D))$ oraz pamięciowej $O(U\log (U))$.