Omówienie zadania Plażowicze (II etap XXVIII OI)

Na odcinku o długości \(X\) mamy \(n\) punktów (przy czym na obu końcach odcinka też są punkty). Będziemy dodawać nowe punkty, przy czym za każdym razem wybieramy pozycję tak, by zmaksymalizować odległość od najbliższego innego punktu, a w przypadku remisów wybieramy pozycję najbliższą lewego końca. Mamy \(z\) zapytań postaci ,,Gdzie dodamy \(k\)-ty punkt?”

Pierwsze obserwacje

Załóżmy, że dodajemy nowy punkt. Żeby znaleźć najbliższy inny punkt, wystarczy rozważyć sąsiada po lewej i sąsiada po prawej stronie (zawsze istnieją). Załóżmy, że odległość pomiędzy tymi dwoma sąsiadami wynosi \(d\). Skoro chcemy zmaksymalizować odległość od tych dwóch sąsiadów, to najlepiej dodać nowy punkt dokładnie pośrodku tych dwóch sąsiadów, bo wtedy odległość od każdego z nich będzie wynosić \(\frac{d}{2}\).

Zatem opłaca się wstawić nowy punkt pomiędzy takie dwa kolejne punkty, dla których odległość \(d\) jest jak największa. I tak postępujemy z każdym kolejnym punktem.

Podzadanie 1

Najprostsza symulacja mogłaby wyglądać następująco. Trzymamy w tablicy lub wektorze kolejne pozycje punktów. Jeżeli chcemy dołożyć nowy punkt, to przeglądamy tablicę w poszukiwaniu najdłuższego przedziału pomiędzy dwoma kolejnymi punktami. Oczywiście takie przejście zajmie nam czas liniowy. Następnie wstawiamy punkt, co wymaga przebudowania tablicy i też zajmie czas liniowy. Ponieważ zrobimy to dla każdego z \(k\) punktów, czas działania to będzie \(O((n+k)k)\).

Aby to przyspieszyć, skorzystamy z kolejki priorytetowej, do której będziemy wkładać długości przedziałów oraz miejsca, gdzie te przedziały występują. Na początek wkładamy wszystkie przedziały pomiędzy istniejącymi punktami. Każdy przedział będzie reprezentowany przez parę postaci \((d, x)\), gdzie \(d\) jest długością przedziału, natomiast \(x\) jest jego początkiem. Takie pary będziemy trzymali na kolejce priorytetowej posortowane nie rosnąco po długości \(d\), a w przypadku remisów posortowane rosnąco po pozycji \(x\).

Gdy chcemy wstawić nowy punkt, to wyciągamy z kolejki priorytetowej pierwszy przedział \((d,x)\). Następnie wstawiamy nowy punkt w środek tego przedziału, czyli na pozycji \(x + \frac{d}{2}\). To powoduje podział przedziału \((d,x)\) na dwa przedziały, czyli do kolejki wrzucamy pary \((\frac{d}{2}, x)\) oraz \((\frac{d}{2}, x + \frac{d}2)\).

Jeżeli kolejkę priorytetową zaimplementujemy jako kopiec binarny, to operacje wstawiania nowych par do kolejki oraz usuwania pary o największym \(d\) będą działały w czasie logarytmicznym od liczby par. Tak więc złożoność to będzie \(O(\log(n + k) \cdot k)\).

Zauważmy, że taka złożoność pozwoli nam zaliczyć podzadanie 1, w którym mamy jedno zapytanie i \(k \leq 10^5\).

Zauważmy, że taka symulacja pozwoliłaby nam również na odpowiadanie na wiele zapytań. Wystarczyłoby jedynie na początku posortować wszystkie zapytania w czasie \(O(z \log z)\). Gdy nowo dodany punkt ma numer taki jak kolejne zapytanie z posortowanej listy, to po prostu zapisujemy sobie na boku odpowiedź dla tego punktu, a po zakończonej symulacji wypisujemy wszystkie odpowiedzi w odpowiedniej kolejności.

Podzadanie 4

Jeżeli przyjrzymy się bliżej pozycjom kolejnych punktów, to możemy dostrzec pewne prawidłowości. Ponieważ każdy przedział dzielimy dokładnie na dwie równe części, to pozycje wszystkich punktów będą się wyrażały liczbami wymiernymi, których mianownik będzie pewną potęgą dwójki. Gdy podzielimy jakiś przedział na dwa kawałki o równej długości, to te dwa kawałki będą występowały na osi obok siebie. Ponadto, każdy z tych kawałków dalej będzie dzielony na mniejsze kawałki.

Co więcej, jeżeli podzielimy lewy z tych kawałków, to następnym krokiem będzie podział prawego z tych kawałków. Wobec tego pierwotny przedział zostanie w tym momencie podzielony na cztery kawałki o długości \(\frac{1}{4}\) pierwotnego przedziału. I znowu, kiedy dojdzie do podziału jednego z tych kawałków, to wiemy, że będziemy musieli zacząć od podziału lewego z nich, a następnie będziemy dzielili wszystkie kolejno, powodując, że ten oryginalny przedział zostanie podzielony na kawałki równej długości \(\frac{1}{8}\) tego przedziału.

Widać zatem, że na naszej kolejce priorytetowej będziemy mieli coraz więcej takich grup sąsiadujących kawałków o równej długości. Wobec tego, zamiast pracowicie wrzucać te wszystkie kawałki na kolejkę, możemy informacje o tych kawałkach skompresować. Będziemy teraz przechowywać na kolejce trójki \((d, x, c)\). Taka trójka oznacza, że mamy do czynienia z \(c\) kawałkami, każdy o długości \(d\). Pierwszy zaczyna się w punkcie \(x\) i są położone obok siebie. To znaczy, że taka trójka odpowiada przedziałom \[(d, x), \, (d, x + d), \, (d, x + 2d), \, \ldots, \, (d, x + (c-1) d).\]

Kiedy taka trójka \((d, x, c)\) zostanie wyciągnięta z kolejki priorytetowej, to możemy jednocześnie dodać \(c\) nowe punkty, w środkach tych przedziałów, czyli na pozycjach \(x + \frac{d}{2} + i \cdot d\) dla \(0 \leq i < c\). Oczywiście nie będziemy zapisywać wszystkich tych punktów, a jedynie dla tych wartości \(i\), które będą nas interesowały z zapytań.

Następnie na kolejkę priorytetową wrzucimy trójkę \((\frac{d}{2}, x, 2c)\), co będzie odpowiadać podzieleniu każdego z tych \(c\) przedziałów na dwa przedziały o długości \(\frac{d}{2}\).

Jaką złożoność będzie miało to rozwiązanie? Zauważmy, że za każdym razem, gdy wyciągamy jakąś trójkę z kolejki priorytetowej, to podwajamy liczbę punktów reprezentowanych przez tę trójkę. Zatem jeżeli pewna trójka na początku reprezentowała tylko jeden punkt, to po wyciągnięciu jej z kolejki jeden raz będzie reprezentowała dwa punkty, po wyciągnięciu jej drugi raz cztery punkty itd. Ogólnie po wyciągnięciu jej \(m\) razy będzie reprezentowała \(2^m\) punktów. Tak więc jeżeli taką trójkę wyciągniemy \(O(\log k)\) razy, to będziemy wiedzieli, że będzie reprezentowała ona co najmniej \(k\) punktów.

Ponieważ możemy tak wyciągać \(n\) początkowych trójek z kolejki, więc sumaryczna liczba operacji na kolejce wyniesie \(O(n \cdot \log k)\). Gdy dodamy \(O(z \log z)\) na posortowanie zapytań, dostajemy złożoność czasową całego rozwiązania \(O(n \log k \log n + z\log z)\).

Pełne rozwiązanie

Aby zaliczyć ostatnie podzadanie, w którym \(n \leq 10^6\), przyda nam się jeszcze jedna drobna obserwacja. Podzielmy sobie trójki reprezentujące przedziały na dwie grupy, które będziemy trzymać na dwóch kolejkach priorytetowych. Pierwsza grupa to będzie \(n - 1\) trójek, które powstały z oryginalnych punktów. Natomiast druga grupa to będą trójki pochodzące z nowych punktów.

Teraz operacja dodania punktów będzie wyglądać następująco: porównujemy długości najdłuższego przedziału z pierwszej i drugiej kolejki, usuwamy ten dłuższy (niech to będzie \(d\)) i wrzucamy na drugą kolejkę długość \(\frac d 2\).

Okazuje się, że nowe przedziały będą zawsze lądowały na końcu drugiej kolejki. Można bowiem pokazać, że ostatni element na drugiej kolejce może być co najwyżej dwa razy mniejszy od największego elementu, który występuje na początku obu kolejek. Tak więc, jeżeli usuniemy dowolny z tych elementów i wrzucimy jego połówkę na drugą kolejkę, to na pewno wyląduje ona na końcu.

To powoduje, że tak naprawdę nie musimy utrzymywać kolejek priorytetowych. Z pierwszej kolejki tylko usuwamy, więc możemy jej elementy posortować nie rosnąco po wartościach \(d\) w czasie \(O(n\log n)\), a następnie przeglądać po kolei.

Natomiast dla drugiej grupy wystarczy zwykła kolejka w tablicy, na której operacje wykonujemy w czasie stałym.

Dzięki temu będziemy mogli usunąć ze złożoności czasowej czynnik \(\log n\), kosztem początkowego posortowania elementów. Takie rozwiązanie ma złożoność \(O(n \log k + n\log n + z\log z)\).

Szczegół techniczny

Pozostała jeszcze jedna techniczna sprawa dotycząca tego, w jaki sposób przechowywać nasze odległości, które będą liczbami wymiernymi. Moglibyśmy oczywiście przechowywać je w postaci ułamków na dwóch zmiennych: w jednej zmiennej trzymalibyśmy wartość licznika, a w drugiej zmiennej wartość mianownika. Ale wszystkie liczby wymierne, które się pojawią podczas działania algorytmu, będą miały mianowniki będące potęgami dwójki. Ponadto znamy ograniczenie na wielkość mianowników, bo wiemy, że nie będziemy dzielić przedziałów więcej niż \(\log k\) razy. Ponieważ \(k \leq 10^9\), więc to będzie nie więcej niż \(30\) razy, zatem mianowniki są ograniczone przez \(2^{30}\).

Tak więc możemy zastosować następujący trik. Na początek wszystkie wartości mnożymy razy \(2^{30}\): jeśli mamy początkową długość przedziału \(d\), to będziemy ją reprezentowali w postaci liczby \(d \cdot 2^{30}\) (taką liczbę musimy trzymać na zmiennej \(64\)-bitowej). Dzięki temu każde dzielenie przez \(2\) będzie odbywało się po prostu na tej jednej zmiennej. Na końcu, gdy będziemy mieli wypisać odpowiedź, wypiszemy po prostu ułamek \(\frac{d}{2^{30}}\). Oczywiście odpowiednio uproszczony, to znaczy zarówno licznik \(d\), jak i mianownik \(2^{30}\) będziemy musieli podzielić przez ich największy wspólny dzielnik.