Informatyczny kącik olimpijski

XORanges

W tym odcinku omówimy rozwiązanie zadania XORanges, które pojawiło się na trzecich zawodach European Junior Olympiad in Informatics (Maribor, Słowenia).

Zadanie (XORanges). Dany jest ciąg $n$ liczb naturalnych $|a = (a1,a2,...,an)$ oraz $q$ poleceń dwóch typów. 1) Zmień wartość $|i$ -tego elementu. 2) Podaj współczynnik przedziału $|ax,ax+1,...,ay.$ Współczynnik przedziału $|a ,a ,...,a x x+1 y$ obliczamy w następujący sposób: dla każdego podsłowa (spójnego fragmentu) tego przedziału liczymy xor jego wartości, następnie xorujemy te wyniki, otrzymując współczynnik przedziału. Przykładowo współczynnik przedziału $(a3,a4,a5)$ wynosi $|a ⊕ a ⊕ a ⊕ (a ⊕ a )⊕ (a ⊕ a )⊕ (a ⊕ a ⊕ a ). 3 4 5 3 4 4 5 3 4 5$ Zaproponuj algorytm, który jest w stanie możliwie szybko wykonać wszystkie polecenia podane na wejściu.

Na początku przyjmijmy, że polecenia typu $1)$ będziemy wykonywali w czasie $|O(1)$ poprzez zmianę wartości $ai. |$ Zatem zajmijmy się odpowiedziami na polecenia typu $2). |$ Załóżmy, że chcemy obliczyć współczynnik $|ax,ax+1,...,ay.$ Na potrzeby artykułu wprowadźmy kilka oznaczeń. Niech:

$[ai;a j]$ oznacza ciąg $(ai,ai+1,...,a j−1,aj ),$
"xor podsłowa $[ai;a j]$ " oznacza wartość $a ⊕ a ⊕ ...⊕ a ⊕ a . i i+1 j −1 j$

Rozwiązanie $|O$
Pierwsze rozwiązanie polega na obliczeniu xora każdego z $|d -d−1- 2$ podsłów, gdzie $d = y− x +1$ i oznacza długość przedziału $[x;y].$ Obliczenie xora podsłowa odbywa się za pomocą metody naiwnej, polegającej na przejściu po wszystkich elementach. Na koniec xorujemy powyższe wyniki. Rozwiązanie dla jednego polecenia działa w czasie $O(n3),$ zatem całkowita złożoność to $|O(q$

Rozwiązanie $|O$
W tym rozwiązaniu, podobnie jak wyżej, obliczymy xor podsłów $|[a ;a ] x y$ (dla wszystkich $′ ′ x ⩽ x ⩽ y ⩽ y$ ) niezależnie. Jednak tym razem, zamiast naiwnej metody, skorzystamy z obserwacji, że:

ax ⊕ ax +1⊕ ...⊕ ay = sy ⊕ sx −1,

gdzie $si = a1 ⊕ a2⊕ ...⊕ ai.$ Ciąg $|s = (s0,s1,s2,...,sn)$ ma analogiczną konstrukcję do ciągu sum prefiksowych i możemy go wygenerować w czasie $|O(n).$ Otóż $s | = 0, 0$ zaś $|s = s ⊕ a i i−1 i$ (dla $i > 0$ ). W ten sposób otrzymaliśmy rozwiązanie działające w czasie $O(q$

Rozwiązanie $|O$
Przypomnijmy proste fakty:

$g ⊕ g = 0$ (dla $|g$ naturalnego),
$g ⊕ 0 = g$ (dla $|g$ naturalnego),
$⊕$ jest operacją łączną i przemienną.

Na podstawie powyższych faktów możemy zauważyć, że do obliczenia współczynnika przedziału wystarczy znać parzystość liczby wystąpień każdego elementu w wyrażeniu je opisującym. Przykładowo:

a3 ⊕ a4⊕ a5 ⊕ (a3⊕ a4) ⊕ (a4⊕ a5) ⊕ (a3⊕ a4 ⊕ a5) = a3⊕ a5,

gdyż $a3$ i $a5$ występują nieparzyście wiele razy w całym wyrażeniu, zaś $|a4$ występuje parzyście wiele razy.

Zastanówmy się, ile razy $ai$ (dla $x ⩽ i⩽ y$ ) występuje we wzorze opisującym współczynnik przedziału $|[ax;ay].$ Innymi słowy chcemy obliczyć, w ilu podsłowach występuje $|a . i$ Niech $| f i$ oznacza tę wartość. Otóż początkiem takiego podsłowa może być element o numerze z przedziału $|[x; i],$ końcem zaś element o numerze z przedziału $[i;y].$

y−i+1 ax, ...,ai−1,ai,ai+1, ...,ay i− x+1

Zatem $| fi = (i− x + 1)(y −i +1).$ Współczynnik przedziału to xor zbioru ${ai x⩽ i ⩽y$ i $| fi$ jest nieparzyste $|}.$ Wyznaczenie tego zbioru realizujemy w czasie $O(n).$ Zatem całe rozwiązanie działa w czasie $|O(q$

Rozwiązanie $|O$
Przed nami rozwiązanie wzorcowe. Polecenie $1)$ będziemy wykonywali nieco inaczej niż poprzednio, ale najpierw opiszemy operację $2).$

Przeanalizujmy parzystości elementów ciągu $f.$ Otóż $| fi$ jest nieparzyste, jeśli $(i− x + 1)$ i $(y − i + 1)$ są nieparzyste. Stąd $fi$ jest nieparzyste wtedy i tylko wtedy, gdy $|x,y,i$ są tej samej parzystości. Zatem jeśli $x$ i $|y$ są różnej parzystości, to odpowiedzią jest $|0.$ W przeciwnym przypadku odpowiedzią jest:

ax ⊕ ax+2⊕ ax+4 ⊕ ...⊕ ay−2⊕ ay.

Chcemy szybko znajdować wartość powyższego wyrażenia. Zauważmy, że jest to xor elementów na pozycjach parzystych lub nieparzystych ciągu $|[ax;ay].$ Niech zatem:

$aN = (a ,0,a ,0,a ,0,a ,0,...), 1 3 5 7$
$aP = (0,a2,0,a4,0,a6,0,a8,...).$

Wówczas dla $|x$ parzystego odpowiedzią jest $aPx⊕ aPx+1⊕ ...⊕ aPy ,$ zaś dla $|x$ nieparzystego odpowiedzią jest $aNx ⊕ aNx+1⊕ ...⊕ aN y .$

Zbudujmy dwa drzewa przedziałowe. Liśćmi pierwszego z nich niech będą wartości ciągu $aN ,$ zaś liśćmi drugiego niech będą wartości ciągu $|aP.$ Pozostałe węzły będą przechowywały xor wartości dzieci. Taka struktura pozwala w czasie $O(log(n))$ znajdować $xor |$ przedziału oraz w tym samym czasie obsługiwać operację zmiany wartości elementu (polecenie typu pierwszego). Zatem całe rozwiązanie działa w czasie $|O(n$