Sumy prefiksowe - zadanie

Question

Witam,

mam zadanie https://www.spoj.com/WSDOCPP/problems/DEN_04_03/ . Myślałem, że wiem jak je rozwiązać, a wręcz że jest łatwe. Okazało się, że nie mogę liniowo przechodzić od jednego końca do drugiego i podmieniać bo przekracza limit czasu. Dowiedziałem się, że muszę wykorzystać tu sumy prefiksowe, jednak nie wiem jak to powinno wyglądać, ani w jaki sposób je zastosować.

Z góry dzięki.

Answer 1

Nie wiem jak tu użyć sumy prefiksowe ale widzę inny sposób.

1) Na starcie w początkowym ustawieniu zliczasz ile jest takich ludzi co mogą sobie przybić piątkę.
2) Możesz zauważyć że jeżeli odwracasz jakieś osoby w przedziale [a, b] to osoby w przedziale [a+1, b-1] przybiją dokładnie tyle samo piątek co wcześniej. Zatem jedyna różnica jest na końcach i początkach przedziałów.
Musisz po prostu zliczyć ilu ludzi zaczęło lub przestało sobie przybijać piątkę i po każdym zapytaniu aktualizować tę liczbę.

Zacząłem jednak teraz wątpić w swoje rozwiązanie, bo nie updatowalibyśmy kierunku ludzi w środku.

 

EDIT:

Dobra to inne rozwiązanie. Zróbmy zamiatanie. Każdy taki przedział rozbijmy sobie na 2 eventy. Początek i koniec i posortujmy te eventy po pozycji. Iterujesz się teraz po kolei po każdym elemencie i w tablicy i pamiętasz w ilu otartych przedziałach ten element się zawiera. Jeżeli jest to liczba parzysta to go nie odwracasz, jeżeli nieparzysta to odwracasz.

Złożoność: (n + qlogq)

 

EDIT 2:

Rzeczywiście wystarczy użyć sumy prefiksowe :)
Zrób tablicę która jeżeli na pozycji x zawiera jakaś wartość to znaczy że ta wartość dodaje się do wszystkich pozycji za x.
Dzięki takiej tablicy można łatwo przetworzyć zapytania. Jak masz zapytanie o przedział [a, b] z wartością c to na pozycji a dodajesz c, a na pozycji b+1 odejmujesz c.

Na koniec wystarczy tylko przeiterować się po tej tablicy sum i policzyć dla każdej pozycji ile przedziałów na nią nachodzi. Jeżeli jest to liczba nieparzysta to gościa odwrócić.
Czas: O(n+q)

Comments

Dokładnie, te 2 rozwiązania są spoko, wydaje mi się, że są one praktycznie takie same. Warto podkreślić, że można zaimplementowac proste drzewo przedziałowe przedział-punkt. Raczej trochę prostsze niż zamiatanie, jak dostajesz operację obróć wszystkie osoby w przedziale [l,p], to na przedziale [l,p] dodajesz jeden, i na koniec osoby obrócone w tym samym kierunku, to te które mają tę samą wartość modulo 2.

A co do zamiatania, to takie klasyczne zadanko na zamiatanie. Jest ich w internecie / na contestach cała masa, może jakieś Cię zainteresują np.: Kinomani - Eliminacje do EJOI 2020, po 14 OIJ, Zadanie Zbrodnia na Piccadilly Circus - potyczki algorytmiczne, oba są na szkopule.