Omówienie zadania NWW (III etap XXX OI)

Wstęp

W zadaniu mamy dany ciąg \(a\) o długości \(n\) oraz zapytania o spójne przedziały tego ciągu w postaci pary liczb \(l, r\). W wyniku zapytania chcemy zwrócić sumę po NWW (największych wspólnych wielokrotnościach) wartości na wszystkich spójnych podciągach ciągu \(a\), których indeksy się w przedziale \([l, r]\). Wypisywaną wartość nazwiemy NWWSUMĄ przedziału \([l, r]\) w ciągu \(a\).

Podzadania 1 oraz 2

Dla każdego zapytania możemy brutalnie sprawdzić wszystkie przedziały zawierające się w \([l, r]\). Możemy poznać NWW wszystkich tych przedziałów w \(O(n^2)\), osiągając złożoność czasową \(O(qn^2)\). Możemy zmodyfikować to rozwiązanie do złożoności czasowej \(O(q+n^2)\) poprzez tablicowanie wyników jako \(NWW[l][r]\) oraz \(\mathit{dp}[l][r]\). W \(\mathit{dp}[l][r]\) trzymamy NWWSUMĘ dla przedziału \([l, r]\) w ciągu \(a\). Dla każdej pary \(l, r\), takiej, że \(l < r\), zachodzi

• \(\mathit{dp}[l][r] = nww(\mathit{dp}[l][r-1], a[r])\),
• \(\mathit{dp}[l][r] = \mathit{dp}[l][r-1]\)\(+\mathit{dp}[l+1][r]-\mathit{dp}[l+1][r-1]\).

Na zapytanie odpowiedź odzyskujemy w czasie \(O(1)\).

Kluczowe zauważenie

Faktem jest, że dla dowolnych liczb naturalnych \(a, b\) zachodzi \(nww(a, b) = \frac{ab}{nwd(a, b)}\). Aby nieco lepiej zrozumieć rozpatrywane przez nas zaraz podzadania, zastanówmy się najpierw nad czynnikiem \(nwd(a, b)\). Niech \(c\) będzie ciągiem liczb całkowitych z pewnego zakresu \([1, n],\) o długości \(m\), a \(c'\) takim ciągiem, że \(c'_i = nwd(c_1, c_2,\ ..., c_i)\). Niezwykle ważnym zauważeniem jest to, że zbiór wartości ciągu \(c'\) jest rozmiaru \(O(\log n)\).

Aby to sobie łatwiej uzmysłowić, warto spostrzec, że ciąg \(c'\) jest nierosnący. Jest tak, ponieważ dla dowolnych naturalnych \(a, b\) zachodzi \(nwd(a, b) \leq a\). Następnie, widzimy, że multizbiór dzielników pierwszych liczby \(c_1\) jest rozmiaru właśnie \(O(\log n)\). Dla \(i = 1\) zachodzi \(c'_i = c_i\) oraz dla każdego \(i > 1\) zachodzi \(c'_i = nwd(c'_{i-1}, c_i)\). Dzięki temu widzimy, że \(c'_i\) może co najwyżej stracić dzielniki pierwsze względem \(c'_{i-1}\), a ta sytuacja zajdzie co najwyżej \(O(\log n)\) razy.

Podzadanie 3

W tym podzadaniu mamy do czynienia tylko z jednym zapytaniem, więc bez straty ogólności możemy założyć, że dotyczy ono całego ciągu. Aby rozwiązać tę część zadania, będziemy iterować się od początku ciągu, w każdym momencie rozpatrując przedziały mające swój prawy koniec w miejscu iteratora (nazwijmy tę pozycję \(r\)). Będziemy również utrzymywać stos, na którym będą takie indeksy \(i\), dla których \(c'_{i+1} \neq c'_i)\). Aktualizacja tego stosu zajmuje \(O(\log n)\) kroków.

Dodatkowo, utrzymujemy drzewo przedziałowe umożliwiające operacje:

• Przemnożenie przez pewną wartość \(v\) na przedziale,
• Zapytanie o sumę na przedziale.

Zdefiniujmy ciąg \(X\) w ten sposób, dla każdego \(i \leq r\) zachodzi \(X_i = \frac{1}{c'_i} \prod_{j = i}^{r} a_j\), czyli \(X_i\) to iloczyn wartości \(a_i\) na przedziale od \(i\) do \(r\), podzielony przez \(c'_i\), czyli NWW wartości z tego przedziału. Nasze drzewo postawimy właśnie na tym ciągu.

Drzewo aktualizujemy podczas aktualizacji stosu, przemnażając przez odpowiednie wartości prefiksy drzewa, w momencie, w którym usuwamy bądź modyfikujemy wartość na stosie. Po zaktualizowaniu drzewa dla odpowiedniego prefiksu, dodajemy do wyniku sumę wartości na tym prefiksie.

Rozwiązanie wzorcowe

Aby zdobyć maksymalną liczbę punktów i szybko odpowiadać na wiele zapytań, będziemy musieli nieco zmodyfikować drzewo przedziałowe.

Wprowadźmy do użycia ciąg \(Y\) do długości \(n\), początkowo wypełniony samymi zerami. Chcielibyśmy, aby nasze nowe drzewo przedziałowe obsługiwało dodatkowo operacje:

• \(X_i\) += \(Y_i\), dla każdego \(i: 1 \leq i \leq n\) \((a)\),
• Zapytanie o sumę wartości \(Y\) na przedziale.

Na zapytania będziemy odpowiadać offline. Zauważmy, że po zaktualizowaniu naszego drzewa \(r\)-tego prefiksu, wynikiem dla zapytania mającego prawy koniec w obecnym \(r\), lewy zaś w pewnej wartości \(l\), jest po prostu zapytanie o sumę wartości \(Y\) na przedziale \([l, r]\)!

Pozostało nam jedynie wymyślić, w jaki sposób wykonywać operację \((a)\). Niech \(s_x\) oznacza sumę z tablicy \(X\) na danym przedziale, zaś \(s_y\) sumę z tablicy \(Y\) na danym przedziale. Zauważmy, że każdą operację, którą chcielibyśmy przeprowadzić na naszym drzewie przedziałowym, możemy reprezentować jako przekształcenie postaci pary \((a, b)\), które parę \((s_x, s_y)\) zamienia na \((a\cdot s_x, s_y + b\cdot s_x)\).

Przykładowo, przemnożenie pewnego przedziału razy pewną stałą \(v\) przedstawimy jako parę \((v, 0)\), zaś operację \((a)\), jako parę \((1, 1)\). Ponadto, nietrudno zauważyć, że przekształcenie to jest łączne, więc możemy go użyć w drzewie przedziałowym.

Ostatecznie osiągamy więc złożoność czasową \(O(n\log^2 n)\).