Omówienie zadania Marudny Bajtazar (II etap XXVII OI)

W zadaniu mamy dany ciąg bitów o długości \( n \), który oznaczymy jako \( S \). \( m \) razy zmienimy pewien bit (0 na 1 lub 1 na 0). Dla każdej aktualizacji chcemy określić długość najkrótszej maski bitowej, która nie występuje w \( S \) jako spójny fragment.

Zauważmy, że taka maska będzie bardzo krótka. Spójnych fragmentów długości \( k \) jest w całym ciągu \( n-k+1 \). Natomiast liczba różnych masek \( k \)-bitowych wynosi \( 2^k \). W takim razie możemy ustalić \( d \) jako najmniejszą taką liczbę naturalną, że \( 2^d > n-d+1 \). \( d \) jest oczywiście wielkości \( O(\log n) \).

Wstępne obliczenia

Będziemy dla każdego \( k \in \{1, \dots, d-1\} \) utrzymywać wartość \( r_k \) - liczbę różnych masek \( k \)-bitowych, które są spójnymi fragmentami \( S \). Wtedy istnieje maska długości \( k \), która nie występuje w \( S \) wtedy i tylko wtedy, gdy \( r_k < 2^k \).

Aby sprawnie aktualizować \( r_k \), będziemy utrzymywać \( t_{k,j} \) - liczbę wystąpień w \( S \) maski \( k \)-bitowej równej \( j \). Aby zainicjować \( t \), musimy dla każdego \( i \in \{1, \dots, n\} \) przejść po wszystkich maskach zaczynających się w \( i \), które mają długości mniejsze niż \( d \). W takim razie łączny czas potrzebny na te obliczenia to około \( dn = O(n \log n) \). Ponieważ dla długości \( k \) mamy \( 2^k \) różnych masek, to pamięć potrzebna na \( t \) to łącznie \(\sum_{1 \leq k < d} 2^k = O(n)\).

Aktualizacje

Przy aktualizacji \( S \) przechodzimy po wszystkich maskach (długości \( < d \)), które zawierają aktualizowany bit, zmniejszając odpowiednie wartości \( t \). Następnie zmieniamy bit i przechodzimy po tych maskach jeszcze raz, tym razem zwiększając odpowiednie wartości \( t \). Przy zmniejszaniu i zwiększaniu \( t \), aktualizujemy \( r \):

• Jeśli \( t_{k,j} \) po zmniejszeniu stało się zerem, to zmniejszamy \( r_k \) o 1 (pewna maska długości \( k \) przestała występować w \( S \)).
• Jeśli \( t_{k,j} \) po zwiększeniu przestaje być zerem, to zwiększamy \( r_k \) o 1 (pojawia się maska długości \( k \), której dotąd nie było w \( S \)).

Przejście po odpowiednich maskach zajmuje \( O(\log^2 n) \). W takim razie wszystkie aktualizacje zajmą nam \( O(m \log^2 n) \).

Zapytania

Przy zapytaniu wypiszemy najmniejsze takie \( k \), że \( r_k < 2^k \) (bo wtedy pewna maska długości \( k \) nie występuje w \( S \)). Jeśli nie istnieje takie \( k \), wypiszemy \( d \), ponieważ nie mogą występować w \( S \) wszystkie maski tej długości. A więc odpowiedź na zapytanie zajmuje \( O(\log n) \) czasu.

W takim razie rozwiązanie działa w złożoności czasowej \( O(n \log n + m \log^2 n) \) oraz pamięciowej \( O(n) \).