Omówienie zadania Deszcze meteorów (III etap XXXIII OI)
Treść zadania
Sytuację z zadania możemy wyobrazić sobie jako prostokąt o wymiarach \(n \times 86\,400\,000\), jak na rysunku w treści zadania. Niech oś \(x\) będzie pozioma, a oś \(y\) pionowa. W prostokącie mamy zakolorowanych \(m\) parami rozłącznych pionowych pasków, czyli pionowych prostokątów o szerokości 1. Niech \(P(x,y)\) oznacza maksymalną liczbę kolejnych zamalowanych pól w prawo od \((x,y)\), tj. \((x,y),(x+1,y),(x+2,y),\ldots\). Dla każdego \(x \in \{1,\ldots,n\}\) chcemy wyznaczyć takie \(y\), które maksymalizuje wartość \(P(x,y)\). Tak naprawdę wystarczy nam znać dla danego \(x\) wartość \(\max_y P(x,y)\), a niekoniecznie obliczać to konkretne \(y\).
Pierwsze obserwacje i prostsze rozwiązania
Załóżmy, że zamalowujemy wprost pola w prostokącie jak w opisie powyżej. Niech \(Y\) będzie maksymalną współrzędną \(y\) zamalowanego pola.
Jeśli zadanie rozwiążemy po prostu implementując polecenie, to dla każdego z \(O(nY)\) pól \((x,y)\) musimy pójść co najwyżej o \(n\) w prawo, co daje złożoność \(O(n^2 Y)\). Takie rozwiązanie pozwalało zaliczyć drugie podzadanie.
W zadaniu wygodnie rozpatrywać współrzędne \(x\) od prawej do lewej, stosując programowanie dynamiczne do wyznaczania wartości \(P(x,y)\). Jeśli pole \((x,y)\) nie jest zamalowane, to \(P(x,y)=0\), a w przeciwnym razie \(P(x,y)=P(x+1,y)+1\). W ten sposób wartość \(P(x,y)\) wyznaczamy w czasie stałym. Poprawia to złożoność wcześniejszego rozwiązania do \(O(nY)\), co pozwalało dodatkowo zaliczyć trzecie podzadanie.
Jest dużo możliwych wartości \(y\), ale co najwyżej \(2m\) z nich jest faktycznie dla nas istotnych. Możemy na początku przenumerować wszystkie współrzędne \(y\) pionowych pasków do wartości z zakresu od 1 do \(2m\) (czas \(O(m \log m)\)). Odtąd możemy przyjąć, że \(Y \le 2m\). Nasze wcześniejsze rozwiązanie działa wtedy w czasie \(O(n\min(Y,m)\,+\,m \log m)\), co pozwala zaliczyć wszystkie podzadania od 1 do 4.
Dobre rozwiązanie
Aby przyspieszyć rozwiązanie oparte na programowaniu dynamicznym możemy użyć drzewa przedziałowego. Drzewo to indeksujemy współrzędnymi \(y\). Dla danego \(y\) w drzewie przechowujemy wartość \(P(x,y)\) dla aktualnie rozważanej współrzędnej \(x\). Takie drzewo musi wspierać następujące operacje na indeksach z zakresu \(O(m)\):
- dodaj 1 na przedziale (odpowiadającym pionowemu paskowi)
- ustaw 0 na przedziale (odpowiadającym przerwie między pionowymi paskami)
- podaj maksimum z wartości przechowywanych w drzewie (jako \(\max_y P(x,y)\))
Można zaimplementować takie drzewo tak, aby każda operacja działała w czasie \(O(\log m)\), choć wymaga to trochę doświadczenia. Operacji mamy \(O(n+m)\), co daje rozwiązanie działające w czasie \(O((n+m) \log m)\). Takie rozwiązanie przechodziło wszystkie podzadania.
Lepsze rozwiązanie
Możemy znacznie uprościć zestaw wymaganych operacji na drzewie przedziałowym, jeśli dla każdego pola będziemy przechowywać wartość \(P'(x,y)=P(x,y)+x\). Wtedy dla danego \(x\) wystarczy wyznaczyć maksimum z przechowywanych wartości i odjąć od niego \(x\).
Jeśli pole \((x,y)\) jest zamalowane, to mamy
\[ P'(x,y)\,=\,P(x,y)+x\,=\,P(x+1,y)+1+x\,=\,P'(x+1,y) \]
czyli wartość \(P'(x,y)\) nie zmienia się przy przejściu z \(x+1\) do \(x\). Jeśli zaś pole nie jest zamalowane, to mamy \(P'(x,y)=0+x=x\). Tak więc wystarczy dla każdego maksymalnego niezamalowanego pionowego paska ustawić we wszystkich jego polach wartość \(x\).
Potrzebujemy zatem zaimplementować drzewo przedziałowe z następującymi operacjami:
- ustaw określoną wartość na przedziale
- podaj maksimum z wartości przechowywanych w drzewie
Jest to już dosyć standardowe drzewo przedziałowe typu przedział-przedział (z leniwą propagacją wartości). Więcej na temat takich drzew można przeczytać np. w książce Przygody Bajtazara. Każda z operacji działa w czasie \(O(\log m)\), co także daje złożoność \(O((n+m) \log m)\), jednak implementacja jest istotnie prostsza niż w poprzednim rozwiązaniu.