poniedziałek, 25 listopada 2013

17214. Festyn w Bajtlandii [AL_12_11]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_11
http://pl.spoj.com/problems/AL_12_11

Skrócony opis problemu:
Jest $n$ wież o danych wysokościach oraz $q$ zapytań.
TODO



Rozwiązanie:
Aby rozwiązać to zadanie trzeba znać się trochę na teorii gier, a konkretnie grach NIM. Zapytanie dla $b=1$ to zatem pytanie o wartość XOR wszystkich elementów od $a$ do $b$. Jeśli ów XOR jest niezerowy, to gracz A wygra. Z kolei dla zapytania $b=0$ powinniśmy zXORować wieże od $a$ do $b$ o $x$.

Od razu widać, że naiwna metoda - przechodzenia wszystkich wież od $a$ do $b$ jest za wolna. Mielibyśmy bowiem złożoność $O(q \cdot n)$, co dla maksymalnych testów wynosi $10^{12}$, a więc dużo za dużo. Bardziej zaawansowanym algorytmikom od razu na myśl przychodzi drzewo [przedziałowe]. Nie będę tutaj tłumaczył idei drzewa oraz operacji na nim, lecz odeślę niewtajemniczonych do naprawdę znakomitego poradnika dot. drzew przedziałowych.

Mamy tutaj do czynienia z drzewem przedział-przedział. Na marginesie, w drzewach punkt-przedział wstawiamy punkty i pytamy o przedział, w drzewach przedział-punkt wstawiamy przedziały i pytamy o punkt, a w zadaniach przedział-przedział wstawiamy i pytamy o przedziały.

Drzewa przedział-przedział bazują na metodzie tzw. leniwej propagacji (ang. lazy propagation). Polega ona na tym, że kiedy dodajemy jakiś przedział do drzewa, to nie aktualizujemy wszystkich wierzchołków tego przedziału. Gdybyśmy to robili, to drzewa byłyby przecież jeszcze gorsze od naiwnego algorytmu, gdyż w drzewie jest $2n-1$ komórek (wierzchołków), więc wykonywalibyśmy prawie 2 razy więcej operacji niż aktualizując zwyczajnie tablicę. A zatem, aktualizujemy tylko niezbędne wierzchołki. Np. dla przedziału 0..5 aktualizujemy tylko wierzchołki opisujące 0..3 oraz 4..5. Ich ilość jest logarytmiczna, gdyż najgorszym przypadkiem jest przedział $0..n-1$ - wtedy dla $n=8$ bierzemy przedziały 0..3, 4..5 oraz 6..6 - wszystkie możliwe wielkości drzew (oprócz największego, gdyż dla maksymalnego zapytania 0..7 mamy tylko 1 wierzchołek do zaktualizowania).

Musimy jednak jakoś pamiętać, które wierzchołki muszą być zaktualizowane. Możemy po prostu trzymać w tablicy wartość $x$ przez którą powinniśmy przeXORować cały przedział. Jeśli $update[node] = 0$ to znaczy, że wierzchołek $node$ ma aktualną wartość.

Kiedyś jednak trzeba te wierzchołki aktualizować. Najlepiej dopiero wtedy, gdy je potrzebujemy, a więc podczas zapytania o przedział. Dostawszy jakiś przedział $a..b$ musimy aktualizować wszystkie napotkane wierzchołki (tak, by po przejściu miały wartość 0 w tablicy $update$).

Skoro już rozumiemy ideę leniwej propagacji, wypadałoby wejść w szczegóły implementacyjne. W tablicy $tree$ będziemy trzymać wartość XOR całego przedziału reprezentowanego przez dany wierzchołek. Np. w $tree[3]$ reprezentującego dla $n=8$ przedział 4..7 będziemy mieli $a_4 \oplus a_5 \oplus a_6 \oplus a_7$. Dzięki temu, gdy będziemy chcieli zaktualizować przedział w wierzchołku $node$ wystarczy, że zrobimy $tree[node] \verb!^!= update[node]$, następnie oznaczymy dzieci (jeśli $node$ nie jest liściem) do zaktualizowania i wyzerujemy $update[node]$. Wszystko ok? Nie! Pomyślmy co będzie dla małego przedziału 2..3, dla którego mamy $tree[2..3]=0$ oraz $update[2..3]=5$. Po aktualizacji będziemy mieli $tree[2..3]=5$, a czy jest to poprawny wynik? Nie, gdyż parzysta ilość operacji XOR się redukuje. $3 \oplus 6 \oplus 5 \oplus 5 = 3 \oplus 6$. A zatem aktualizujemy $tree$ tylko gdy długość przedziału jest nieparzysta.

Najłatwiej będzie zaimplementować wszystko rekurencyjnie. Zacznijmy najpierw od aktualizacji drzewa (a więc dodania wież). Chcemy dodać wieże dla każdej komórki w przedziału 0..4. Wywołajmy zatem funkcję $update$ dla wierzchołka 1 (będącego korzeniem drzewa) oraz pełnego przedziału 0..7 (dla $n=8$). Przedział ten jest ewidentnie za szeroki, więc dzielimy go na 2 połowy: 0..3 oraz 4..7 i idziemy np. w lewo. Przedział 0..3 zawiera się całkowicie w naszym przedziale, więc nie aktualizujemy go (jako że jego długość jest parzysta) i oznaczamy jego dzieci do aktualizacji (gdyż ma dzieci) i kończymy pracę (dla tego wywołania). Musimy zrobić $tree[0..3] \oplus = x \oplus update[0..3]$ - nie tylko XOR $x$, ale także XOR $update[0..3]$, gdyż po aktualizacji musimy wyzerować $update[0..3]$. A zatem również dzieci XORujemy przez $x \oplus update[0..3]$, a dopiero po tym zerujemy $update[0..3]$. Następnie wracamy się i idziemy w prawo (gdyż nasz przedział nie jest do końca pokryty). Przedział 4..7 nie zawiera się tym razem w interesującym nas przedziale 0..4. Dzielimy go więc na 2 połowy i idziemy w lewo, do 4..5. Tutaj tak samo, więc ponownie dzielimy i idziemy do 4..4. W końcu nasz przedział się zawiera w 0..4, więc go aktualizujemy (jako że jego długość jest nieparzysta), ale nie oznaczamy jego dzieci do aktualizacji, gdyż jest to liść. Wracamy do 4..5 i idziemy w prawo, do 5..5. Widzimy, że jest to poza naszym przedziałem, więc ignorujemy ten przedział, nic nie robiąc. Wracamy do 4..7 i idziemy do 6..7, które znów jest poza przedziałem, więc też ignorujemy. Koniec. W trakcie musimy oczywiście XORować nasz wynik wartościami wszystkich wierzchołków. które zawierały się w naszym przedziale. Na początku możemy ustawić wynik na 0, gdyż $0 \oplus x = x$ (0 jest elementem neutralnym ze względu na operację XOR).

Dla zapytań typu $b=0$ (pytających o XORa przedziału $a..b$) przechodzimy drzewo w taki sam sposób, tylko wykonując inne operacje. Jeżeli nasz przedział z wywołania rekurencyjnego (a nie zapytania) jest poza przedziałem z zapytania, to ignorujemy go i zwracamy dla niego 0 (wiedząc, że 0 się poprawnie zXORuje z pozostałymi wartościami i nie zepsuje nam wyniku). Następnie, jeśli widzimy, że $update[node]$ jest niezerowe, to znaczy, że musimy zaktualizować przedział, czyli postąpić dokładnie tak samo jak przy aktualizacji. Jeżeli przedział z wywołania zawiera się całkowicie w przedziale z zapytania, to go zwracamy. W przeciwnym wypadku dzielimy przedział na dwie części i zwracamy XORa ich wywołań rekurencyjnych (które de facto również zwrócą nam XORa wszystkich liczb w tamtych przedziałach).

Złożoność: $O(q \log n)$, gdyż mamy $q$ zapytań, a każde (niezależnie od typu) wykonuje logarytmiczną ilość operacji.

Algorytm:
int tree[MAX_N*2], upd[MAX_N*2], st, end;


// dodaj element do drzewa
void insert(int a, int v, M)
{
    a += M-1;
    tree[a] ^= v;
    while(a > 1)
        a /= 2,
        tree[a] = tree[a*2] ^ tree[a*2+1];
}


int update(int node, int b, int e, int x)
{
    // jeśli przedział wywołania jest poza przedziałem zapytania to go zwróć, żeby poprawnie zaktualizować rodzica - patrz return na końcu funkcji (jeśli aktualizujemy noda jako XORa jego dzieci, to musimy zwrócić wartość obu dzieci, nawet jeśli są poza przedziałem)
    if(e < st || b > end)
        return upd[node] && (e-b+1)%2 ? tree[node]^upd[node] : tree[node];
    const int l = node*2, r = l+1, m = (b+e)/2;
    // jeśli przedział wywołania zawiera się w przedziale zapytania
    if(b >= st && e <= end)
    {
        // aktualizuj jeśli długość przedziału jest nieparzysta
        if((e-b+1)%2)
            tree[node] ^= x^upd[node];
        // aktualizuj dzieci jeśli istnieją (nie istnieją jeśli b = e, bo wtedy wierzchołek jest liściem)
        if(b != e)
            upd[l] ^= x^upd[node],
            upd[r] ^= x^upd[node];
        upd[node] = 0;
        return tree[node];
    }
    return tree[node] = update(l, b, m, x) ^ update(r, m+1, e, x);
}


int query(int node, int b, int e)
{
    const int l = node*2, r = l+1, m = (b+e)/2;


    // ignorujemy przedział jeśli jest poza przedziałem zapytania
    if(e < st || b > end)
        return 0;
    // jeśli wierzchołek wymaga aktualizacji
    if(upd[node])
    {
        // aktualizuj go jeśli ma nieparzystą długość
        if((e-b+1)%2)
            tree[node] ^= upd[node];
        // aktualizuj jego dzieci jeśli je ma
        if(b != e)
            upd[l] ^= upd[node],
            upd[r] ^= upd[node];
        upd[node] = 0;
    }
    // jeśli przedział wywołania zawiera się w całości przedziału zapytania, to zwróć jego wartość
    if(b >= st && e <= end)
        return tree[node];
    // zwróć XORa obu połówek
    return query(l, b, m) ^ query(r, m+1, e);
}


int main()
{
    int q, x, y, n, M = 1;


    get(n, q);
    // M jest ilością wierzchołków w drzewie
    while(M < n)
        M <<= 1;
    // inicjalizuj drzewo
    for(int i = 1; i <= n; ++i)
        get(x),
        insert(i, x, M);
    while(q--)
    {
        get(x, st, end);
        if(x)
            print(query(1, 1, M) ? "A" : "B");
        else
            get(y),
            update(1, 1, M, y);
    }
}

Optymalizacje:
Sporo operacji można wykonać na bitach.
  • e-b+1&1 zamiast (e-b+1)%2
  • e+b>>1 zamiast (e+b)/2
  • a >>= 1 zamiast a /= 2
  • node<<1 zamiast node*2

Brak komentarzy:

Prześlij komentarz