Omówienie zadania Rzeki (III etap XXIX OI)

Mamy \(n\) pionowych rzek i \(m\) poziomych rzek ułożonych w kratkę. Niektóre rzeki są czyste (i można z nich brać wodę), a niektóre brudne. Na każdym skrzyżowaniu rzek znajduje się miasto, wobec tego mamy \(nm\) miast. Koszt dostawy wody do danego miasta to odległość tego miasta od najbliższej czystej rzeki.

W zadaniu mamy obsłużyć \(z\) operacji: każda dotyczy albo zmiany statusu rzeki (z czystej na brudną lub na odwrót), albo zapytanie o maksymalną liczbę miast, do których możemy dostarczyć wodę, jeżeli dysponujemy pewnym budżetem \(C\).

Podzadanie 1

W dwóch tablicach pamiętamy, jaki jest status każdej z rzek, wobec tego operacja zmiany statusu to po prostu uaktualnienie jednego bitu (w czasie stałym).

Dla operacji zapytania obliczymy sobie koszty dostawy dla wszystkich miast zwykłym algorytmem BFS. Najpierw kolejkę inicjujemy wszystkimi miastami, które leżą nad czystymi rzekami (będą miały odległość 0). Następnie wykonujemy zwykłego BFS-a na grafie, w którym każde miasto połączone jest z czterema sąsiednimi. To zrobimy w czasie \(O(nm)\).

Przy ustalonym budżecie \(C\) suma odległości do miast, które chcemy wziąć, musi być \(\leq C\). Wobec tego opłaca nam się brać miasta o najmniejszych odległościach – możemy na bieżąco odejmować odległości znajdowanych miast od \(C\), dopóki nie zejdziemy z budżetem poniżej \(0\). W wyniku zwracamy liczbę dodanych miast.

Całe rozwiązanie ma złożoność \(O(znm)\).

Podzadanie 3

Zauważmy, że czyste rzeki dzielą płaszczyznę na pewne prostokąty. Jeżeli mamy dany prostokąt wielkości \(w \times h\), to możemy obliczyć, ile miast w danej odległości będzie znajdowało się w tym prostokącie. Miast w odległości \(1\) będzie dokładnie \(2 (w + h - 8)\), czyli liczba punktów kratowych na prostokącie o rozmiarach \((w - 2) \times (h - 2)\).

Miast w odległości \(2\) będzie o \(8\) mniej, ponieważ oba boki prostokąta zmniejszamy o \(2\), i generalnie miast w odległości \(i\) będzie \(2 (w+h) - 8(i+1)\). To wyliczenie możemy kontynuować, aż boki zejdą się ze sobą, co da nam złożoność \(O(\min(h,w))\), przy czym osobno musimy rozważyć przypadek, kiedy mniejszy bok prostokąta ma długość parzystą, a osobno, kiedy ma długość nieparzystą.

To nam daje pomysł na rozwiązanie, żeby utrzymywać tablicę, gdzie \(count[d]\) to po prostu liczba miast w odległości \(d\). Każde zapytanie o liczbę miast w danym budżecie zrealizujemy w czasie długości tej tablicy, czyli \(O(\max(n,m))\). Wystarczy bowiem iterować się po tej tablicy, rosnąco po \(d\), odejmując od naszego budżetu wartości \(count[d] \cdot d\) tak długo, jak możemy.

A jak zrealizować operację zmiany statusu rzeki? Jeżeli jest to operacja dodania nowej rzeki, to zauważmy, że dzieli nam ona pewne prostokąty na dwie części. Wobec tego dla każdego takiego podziału możemy wziąć stary prostokąt i odjąć w tabelce \(count\) jego wkład, a następnie rozważyć dwa prostokąty powstałe po podziale i dodać w tabelce \(count\) ich wkłady. Ponieważ czas uaktualnienia tabelki \(count\) to jest minimum z długości boków prostokątów, wobec tego sumaryczny czas dla pionowej rzeki będzie ograniczony przez \(O(m)\), a dla poziomej rzeki przez \(O(n)\). Musimy tylko pamiętać o tym, żeby osobno rozpatrzyć prostokąty, które dotykają brzegów planszy, ponieważ dla nich wzory będą trochę inne.

Ostatecznie uzyskujemy rozwiązanie o złożoności \(O(z (n + m))\).

Podzadanie 2

Przejdziemy teraz do omówienia drugiego podzadania, w którym każda pozioma rzeka jest brudna. Więc będą nas interesowały tylko rzeki pionowe i każda z nich będzie miała na sobie \(m\) miast (wszystkie o tym samym koszcie dostawy). Zauważmy, że koszty dla miast leżących między dwoma czystymi rzekami tworzą dwa ciągi arytmetyczne: jeden rosnący i jeden malejący (przy czym znowu mamy dwa przypadki w zależności od parzystości odległości między rzekami).

Podobnie jak w poprzednim rozwiązaniu, wstawienie nowej rzeki powoduje, że musimy wyrzucić ciągi arytmetyczne leżące pomiędzy rzeką na lewo od nowo wstawionej i na prawo od nowo wstawionej, a następnie dorzucić ciągi arytmetyczne pomiędzy wstawioną rzeką a tą z lewej oraz pomiędzy wstawioną rzeką i tą z prawej. Dla znalezienia długości tych ciągów arytmetycznych istotna jest tylko odległość między lewą i prawą rzeką oraz między wstawianą rzeką i lewą i prawą. Te odległości łatwo znaleźć, trzymając pozycje czystych rzek na strukturze set i znajdując w czasie \(O(\log n)\) poprzednika i następnika.

Idea jest taka, że znowu będziemy chcieli trzymać coś w rodzaju tabelki \(count\). Dodanie ciągu arytmetycznego kosztów \(0,1,\ldots,d\) odpowiada dodaniu \(1\) na prefiksie tabelki \(count\) o długości \(d+1\) (pamiętając, że na końcu liczbę miast uzyskamy, przemnażając te wartości przez \(m\)).

Będziemy chcieli odpowiadać na zapytania o liczbę miast na przedziałach, czyli \(M = \sum_{0 \leq i < d} count[i] \cdot m\) oraz o sumę kosztów dostawy na przedziałach, czyli \(S = \sum_{0 \leq i < d} count[i] \cdot i \cdot m\).

Okazuje się, że możemy te sumy uaktualniać na drzewie przedziałowym. Załóżmy, że chcemy obliczyć wartości \(M\) i \(S\) dla pewnego przedziału bazowego o długości \(d\) na podstawie wartości w lewym synu oraz wartości w prawym synu. Oczywiście wartość \(M\) w całym przedziale to jest suma wartości z obu synów: \[M = M_L + M_R.\] Dla wartości \(S\) jest już trochę trudniej. Zakładamy, że w każdym przedziale bazowym mnożymy kolejne wartości przez kolejne liczby naturalne, zaczynając od 0. Wobec tego wkład z lewego przedziału bazowego będzie poprawny, czyli po prostu bierzemy \(S_L\). Ale we wkładzie z prawego przedziału bazowego będziemy mieli za mało, a dokładnie na każdej pozycji będziemy musieli dodać \(d/2\) razy wartość tej pozycji, przy czym \(d/2\) jest długością lewego przedziału: \[S = S_L + (S_R + d/2 \cdot M_R).\]

Umiemy zatem w czasie stałym uaktualniać wartości węzłów w drzewie przedziałowym.

Więc jeżeli zaimplementujemy to na drzewie, w którym możemy dodawać stałą wartość na prefiksie, to operacja zmiany statusu rzeki będzie realizowana w czasie \(O(\log n)\). Natomiast operacja zapytania o liczbę miast dla ustalonego budżetu wymaga znalezienia takiego prefiksu w naszym drzewie przedziałowym, że wartość \(S\) tego prefiksu nie przekracza budżetu \(C\), i zwrócenie wartości \(M\) dla tego prefiksu (plus być może kilku dodatkowych miast dla reszty budżetu \(C-S\)). Również tę operację jesteśmy w stanie zrobić w czasie \(O(\log n)\).

Ostatecznie całe rozwiązanie działa w złożoności \(O((z+n+m)\log n)\).

Pełne rozwiązanie

Okazuje się, że rozwiązanie przypadku jednowymiarowego bardzo nam pomoże w przypadku dwuwymiarowym, chociaż wcale niełatwo jest wpaść na pomysł, jak takie dwuwymiarowe uogólnienie mogłoby wyglądać. Kluczowe jest przestawienie myślenia z pojedynczych miast na pionowe rzeki i poziome rzeki, które możemy rozpatrywać niezależnie. Zauważmy bowiem, że jeżeli mamy \(a\) pionowe rzeki w odległości \(d_a\) od czystych rzek i \(b\) poziome rzeki w odległości \(d_b\) od czystych rzek, to mamy \(ab\) miast, których odległość od najbliższej pionowej czystej rzeki wynosi \(d_a\), a od najbliższej poziomej rzeki wynosi \(d_b\). Koszt dla każdego z tych miast to oczywiście \(\min(d_a,d_b)\).

Więc jeżeli stworzymy sobie tabelkę \(a[d]\) (która będzie tabelką \(count\) dla pionowych rzek), oraz tabelkę \(b[d]\) (która będzie tabelką \(count\) dla poziomych rzek), to te tabelki jesteśmy w stanie uaktualniać w czasie logarytmicznym na drzewach przedziałowych, dokładnie tak jak w rozwiązaniu przypadku jednowymiarowego. Oznaczmy sobie wartości \(M\) i \(S\) dla tych tabelek przez \(M^a\), \(S^a\) (dla tabelki \(a\)) oraz \(M^b\), \(S^b\) (dla tabelki \(b\)).

Aby odczytać z tabelek koszt dostawy dla wszystkich miast, robimy następującą sumę (po odległościach \(i\) od pionowych rzek i odległościach \(j\) od poziomych rzek): \[W = \sum_i \sum_j a[i] \cdot b[j] \cdot \min(i,j).\]

W celu szybkiego operowania na takich sumach, znowu użyjemy drzewa przedziałowego. Rozważmy sobie przedział bazowy \([0,d-1]\), który powstaje ze złączenia synów \([0,d/2-1]\) oraz \([d/2,d-1]\). Na poniższym rysunku przedstawiliśmy przykład obliczenia wartości \(W\) dla przedziału długości \(d=8\):

b[7]  0  1  2  3 | 4  5  6  7
      0  1  2  3 | 4  5  6  6
      0  1  2  3 | 4  5  5  5
      0  1  2  3 | 4  4  4  4
      -----------+-----------
      0  1  2  3 | 3  3  3  3
      0  1  2  2 | 2  2  2  2
      0  1  1  1 | 1  1  1  1
b[0]  0  0  0  0 | 0  0  0  0

    a[0]                  a[7]

Sumujemy \(d^2\) wartości, z których każda to przemnożenie \(a[i] \cdot b[j]\) razy wartość z \(i\)-tej kolumny i \(j\)-tego wiersza rysunku. Cały kwadrat o boku \(d\) dzieli się na cztery podkwadraty o boku \(d/2\).

Wkład z dolnego lewego podkwadratu to oczywiście \(W_L\) (czyli wartość \(W\) dla lewego syna). Wkład z górnego prawego podkwadratu to \(W_R + d/2 \cdot M^a_R \cdot M^b_R\) (czyli wartość \(W\) dla prawego syna powiększona dla każdej komórki o \(d/2\) razy liczba miast).

Liczby, przez które mnożymy w pozostałych dwóch podkwadratach, układają się w ciągi arytmetyczne od \(0\) do \(d/2-1\). Zatem wkład dla dolnego prawego podkwadratu to \(M^a_R \cdot S^b_L\), a dla górnego lewego podkwadratu to \(M^b_R \cdot S^a_L\).

Ostateczny wzór rekurencyjny dla naszego drzewa przedziałowego to \[W = W_L + (W_R + d/2 \cdot M^a_R \cdot M^b_R) + (M^a_R \cdot S^b_L) + (M^b_R \cdot S^a_L).\]

Będziemy potrzebowali jeszcze liczyć koszt dostawy dla wszystkich miast w odległości \(\leq d\), czyli dla tych, które mnożone są przez współczynniki \(\min(i,j)\leq d\). Z rysunku widać, że najłatwiej będzie od całej wartości \(W\) odjąć koszt miast w odległościach \(>d\), gdyż będą one również tworzyć kwadrat (więc odpytamy się drzewo przedziałowe o wartość na odpowiednim sufiksie).

Dopracowanie szczegółów tego rozwiązania jest czysto techniczne i zostawiamy je jako zadanie dla Czytelników. Całkowita złożoność czasowa będzie wynosić \(O((z + n + m)\log(n + m))\).