Omówienie zadania Wybredny bajtazar (III etap XXIX OI)

Mamy dane \(n\)-literowe słowo złożone z małych liter od a do e. Wprowadzamy w nim \(m\) modyfikacji, każda postaci \((c_1,c_2,p)\), co oznacza, że \(p\) pierwszych od lewej wystąpień litery \(c_1\) zamieniamy na literę \(c_2\). Należy wypisać słowo po wszystkich modyfikacjach.

Podzadanie 1

Każdą modyfikację robimy brutalnie, przechodząc całe słowo i zamieniając napotkane litery \(c_1\) na \(c_2\), aż wykonamy \(p\) zamian. Czas działania to \(O(mn)\).

Podzadanie 3

Założenie, że w słowie występują jedynie litery a i b mocno upraszcza zadanie, ponieważ możemy wtedy zauważyć, że każda zmiana litery \(c_1\) na literę \(c_2\) oznacza tak naprawdę ustawienie litery \(c_1\) na pewnym prefiksie naszego słowa. A dokładnie na prefiksie, który kończy się na \(p\)-tym wystąpieniu litery \(c_2\).

Jeśli słowo będziemy reprezentowali jako ciąg zero-jedynkowy, w którym każdej literze a przypiszemy jedynkę, a literze b przypiszemy zero, to zmiana litery a na literę b oznacza, że musimy znaleźć prefiks w tym ciągu o sumie równej \(p\), a następnie zamienić wszystkie cyfry w tym prefiksie na zera. W przypadku przeciwnej zamiany litery b na literę a musimy znaleźć taki prefiks, że jego długość minus suma wynosi \(p\) i zamieniamy wszystkie cyfry na jedynki.

Aby tę operację wykonać szybko, można nad tym ciągiem zbudować drzewo przedziałowe, które umożliwia zapytanie o sumę oraz ustawienie wartości na przedziale. Żeby znaleźć prefiks o odpowiedniej sumie, możemy to zrobić w czasie \(O(\log^2 n)\), korzystając z wyszukiwania binarnego, albo w czasie \(O(\log n)\), poruszając się od korzenia drzewa w dół i odpowiednio wybierając, do którego syna schodzimy. Da to nam rozwiązanie o złożoności \(O(n + m \log n)\).

Struktura drzewa przedziałowego jest dokładnie opisana w książce Przygody Bajtazara.

Pełne rozwiązanie

Ogólne rozwiązanie będzie działać dla dowolnej liczby \(k\) różnych liter (przy czym rozważymy przykład dla \(k=3\)).

Idea jest taka, że operację zmiany liter będziemy wykonywać leniwie i całość będziemy trzymać na drzewie przedziałowym z lazy propagation. Gdy na jakimś fragmencie słowa odpowiadającym przedziałowi bazowemu wykonamy zamianę liter, to chcemy faktycznie nie robić tych zamian w słowie, a jedynie zapisać sobie, że musimy zrobić tę zamianę dla tego węzła.

Idea jest więc taka, że trzymamy tabelkę \(P\) rozmiaru \(k\), która pokazuje, na co przechodzą dane litery. Początkowo ta tabelka jest identycznością, czyli \(P[\texttt{a}] = \texttt{a}\), \(P[\texttt{b}] = \texttt{b}\), \(P[\texttt{c}] = \texttt{c}\). Po wykonaniu zmiany musimy tę tabelkę zaktualizować, np. po zmianie \(\texttt{b}\) na \(\texttt{a}\) tabelka przyjmie postać \(P[\texttt{a}] = \texttt{a}\), \(P[\texttt{b}] = \texttt{a}\), \(P[\texttt{c}] = \texttt{c}\).

Zauważmy, że jeżeli teraz zmienimy literę \(\texttt{a}\) na \(\texttt{b}\), to zmiana będzie dotyczyć wszystkich elementów tabelki, które do tej pory były zmienione na literę \(\texttt{a}\): \(P[\texttt{a}] = \texttt{b}\), \(P[\texttt{b}] = \texttt{b}\), \(P[\texttt{c}] = \texttt{c}\).

Co więcej, możemy złączyć ze sobą dwie takie tabelki. Złączenie tabelki \(P\) z tabelką \(Q\) równą \(Q[\texttt{a}] = \texttt{b}\), \(Q[\texttt{b}] = \texttt{c}\), \(Q[\texttt{c}] = \texttt{a}\), spowoduje powstanie tabelki \(PQ[\texttt{a}] = \texttt{c}\), \(PQ[\texttt{b}] = \texttt{c}\), \(PQ[\texttt{c}] = \texttt{a}\). Jest to istotna operacja, gdyż w procesie lazy propagation będziemy musieli połączyć informację w pewnym węźle z informacją, która przyjdzie od jego ojca.

Tak więc w każdym węźle trzymamy tabelkę \(P\) o wielkości \(k\), w której \(P[c]\) oznacza, że wszystkie litery \(c\) w słowie z dzieci należy zamienić na \(P[c]\).

Będziemy również trzymać tabelkę \(D\), w której \(D[c]\) oznacza liczbę liter \(c\) w słowie węzła już z uwzględnieniem zmian spowodowanych tablicą \(P\). Widać, że tabelkę \(D\) dla danego węzła da się obliczyć na podstawie tabelek \(D\) z jego dzieci oraz tabelki \(P\) z tego węzła. Można to zrobić w czasie \(O(k)\).

Ostatecznie operacja zamiany \((c_1,c_2,p)\) sprowadza się do tego, że w drzewie znajdujemy taki prefiks, dla którego suma wartości \(D[c_1]\) wynosi \(p\), a następnie na całym tym prefiksie domnażamy, używając lazy propagation, tabelkę, w której \(c_1\) zamieniamy na \(c_2\).

Wobec tego każda operacja na drzewie przedziałowym będzie nas kosztować czas \(O(k \log n)\), więc całe rozwiązanie zrobimy w czasie \(O(n + mk \log n)\).