Omówienie zadania Oceny (III etap XXIV OI)

Wstęp

lW zadaniu mamy daną permutację \(p\) o długości \(n\) oraz \(z-1\) aktualizacji postaci pary liczb \((a, b)\). Po każdej aktualizacji, wartości na pozycjach \(a\) oraz \(b\) w permutacji \(p\) zamieniały się miejscami. Dla początkowej permutacji oraz dla każdej kolejnej tworzonej przez zapytania chcemy utworzyć ciąg \(a\) o długości \(n\), który zawiera możliwie najwięcej różnych wartości oraz zachodzą warunki: \((1)\) dla każdego \(j < i : a_j \leq a_i\) oraz \((2)\) dla każdej pary indeksów \((i, j)\), nie zachodzą równocześnie \(p_j > p_i\) oraz \(a_j < a_i\).

Ważna obserwacja

Zauważmy, że ciąg \(a\) musi być niemalejący. Zastanówmy się, dla jakich wartości \(i\) możemy pozwolić sobie na ustawienie \(a_i := a_{i-1}+1.\) Są to takie pozycje \(i\), dla których, każda wartość na sufiksie \([i, n]\) ciągu \(p\) będzie większa niż na prefiksie \([1, i-1]\), aby usatysfakcjonować warunki \((1)\) oraz \((2)\). W takim razie dla każdego takiego \(i\), prefiks ciągu \(p\) o długości \(i-1\) jest permutacją o \(i-1\) elementach.

Rozwiązanie powolne

W takim razie dla każdej aktualizacji możemy pozwolić sobie by w czasie \(O(n)\) (np. trzymając maksymalną wartość na prefiksie) zastosować powyższe zauważenie dla każdej z permutacji, sumarycznie otrzymując złożoność czasową \(O(nz)\).

Druga ważna obserwacja

Chcielibyśmy teraz skonstruować wydajniejszy algorytm. Zastanówmy się więc, czy możemy jakoś przekształcić nasz warunek w taki, który łatwiej jest sprawdzać.

Wiadomo, że suma elementów permutacji jest równa sumie indeksów, na których elementy te się znajdują. Okazuje się również, że żaden ciąg różnowartościowy o długości \(n\), o wyrazach będącymi liczbami naturalnymi, nie będzie się sumował do wartości sumy \(n\) pierwszych liczb naturalnych. Jest to idealna własność dla naszego rozwiązania.

Niech \(\mathit{pf}_i\) będzie sumą \(i\) pierwszych wyrazów w ciągu \(p\). W takim razie \(a_{i+1} = a_i+1\) zachodzi dla wszystkich \(i\), dla których \(\mathit{pf}_i = \frac{i(i+1)}{2}\), czyli \(\mathit{pf}_i - \frac{i(i+1)}{2} = 0\). Niech \(t_i = \mathit{pf}_i - \frac{i(i+1)}{2}\). Nasze zadanie możemy więc przekształcić do znalezienia liczby pozycji, na których \(t_i = 0\).

Rozwiązanie wzorcowe

Pozostało jedynie dobrać odpowiednią strukturę danych do obsługi naszych zapytań przy ciągle zmieniającym się ciągu. Jak to często bywa przy tego typu zadaniach z ciągiem liczb, użyjemy drzewa przedziałowego do rozwiązania naszego uproszczonego zadania.

Nasze drzewo przedziałowe będzie obsługiwać operacje \((x)\) dodania wartości na przedziale oraz \((y)\) podania liczby wystąpień zer w całym ciągu. Szczęśliwie dla nas, \((y)\) możemy zastąpić zwróceniem minimalnej wartości w ciągu oraz liczby wystąpień tej wartości w ciągu, ponieważ \(t_i\) nigdy nie będzie mniejsze niż 0. Nasza aktualizacja w postaci pary \((a, b)\) to teraz odjęcie \(p_a\) na przedziale \([1, a]\), dodanie \(p_a\) na przedziale \([1, b]\) oraz zrobienie analogicznie dla \(b\). Złożoność czasowa naszego rozwiązania to \(O((n+z)\log n)\).

Bonus: Rozwiązanie pierwiastkowe

Istnieje również rozwiązanie działające w czasie \(O((n+z)\sqrt{n})\), które co prawda nie zdobywa kompletu punktów, ale uogólnia się do wielu innych problemów i jest techniką wartą znania. Jest to rozwiązanie polegające na podziale naszego ciągu na bloki o wielkości \(\sqrt{n}\) oraz dla każdego bloku trzymania minimalnej wartości \(t_i\) oraz ilości tych minimów na przedziale. Dodanie wartości na przedziale \([1, x]\), to brutalne zaktualizowanie bloku, w którym znajduje się \(x\), w czasie \(O(\sqrt{n})\), a następnie zaktualizowaniu w każdego bloku znajdującego się przed tym, w którym znajduje się \(x\). Bloków tych jest \(O(\sqrt{n})\), a każda z tych aktualizacji jest w \(O(1)\), więc otrzymujemy czas \(O(\sqrt{n})\) na aktualizację. Odpowiedź na zapytanie odzyskamy w czasie \(O(\sqrt{n})\) poprzez przejście się po wszystkich blokach.