Omówienie zadania Przekaźniki telekomunikacyjne 2 (eliminacje do IOI 2020, dzień 3)

Treść zadania

Dane jest \(n \leq 300\ 000\) przekaźników telekomunikacyjnych. Dla \(1 \leq i \leq n\), \(i\)-ty z nich stoi w punkcie \((x_i, y_i)\) oraz jego moc wynosi \(s_i\). Wtedy dla każdego punktu \((x, y)\) siła sygnału pochodząca z \(i\)-tego przekaźnika jest równa \(\max(0, s_i-\max(|x-x_i|, |y-y_i|))\). Następnie musimy przetworzyć \(m \leq 300\ 000\) zapytań. Każde z nich jest postaci \((x_i', y_i')\) i dla każdego z nich znaleźć maksymalną siłę sygnału w punkcie \((x_i', y_i')\).

Podzadanie 1 – \(n, m \leq 5000\)

W tym podzadaniu możemy dla każdego zapytania \((x, y)\) brutalnie przeglądać wszystkie przekaźniki, obliczyć moc sygnału w punkcie \((x_i', y_i')\) i wypisać największą wartość. Otrzymujemy rozwiązanie działające w czasie \(O(nm)\).

Podzadanie 2 – \(y_i, y_i' = 0\)

To oznacza, że wszystkie punkty znajdują się na jednej prostej, zatem od tej pory możemy zapomnieć o drugiej współrzędnej i rozwiązać zadanie w jednowymiarowej wersji. Wówczas możemy dla każdego zapytania \((x_i', y_i')\) oddzielnie znaleźć największą wartość sygnału pochodzącą od przekaźnika z lewej i z prawej. Skupmy się zatem na znalezieniu największej mocy sygnału z lewej (ponieważ z prawej można problem rozwiązać analogicznie, wystarczy obrócić kolejność wszystkich punktów).

Posortujmy zatem wszystkie punkty (pozycje przekaźników oraz punkty będące zapytaniami) rosnąco względem współrzędnej \(x-\)owej (w przypadku remisów najpierw będziemy chcieli przetworzyć przekaźnik, a następnie zapytanie). Następnie przeglądajmy te punkty od lewej do prawej. Utrzymujmy jednocześnie siłę najsilniejszego dotychczas przetworzonego przekaźnika - możemy tak zrobić, ponieważ w miarę rozważania punktów o coraz większych współrzędnych moc sygnału wszystkich przekaźników z lewej strony w obecnie rozważanym punkcie prostej maleje liniowo. Jeśli trafimy na przekaźnik, to zaktualizujmy największą siłę sygnału w tym punkcie. Z kolei jeśli trafimy na zapytanie, to natychmiast znamy największą moc sygnału pochodzącą z przekaźnika z lewej strony. W ten sposób otrzymujemy rozwiązanie działające w czasie \(O((n+m)\log(n+m))\) z powodu konieczności posortowania danych wejściowych.

Podzadanie 3 – \(|x_i|, |y_i|, s_i, |x_i'|, |y_i'| \leq 300\ 000\)

Ustalmy pewne zapytanie i niech \((x, y) = (x_i', y_i')\) dla pewnego \(i\). Będziemy wykonywać kilka uproszczeń, by rozwiązać to podzadanie. Po pierwsze - całą płaszczyznę możemy obrócić o \(45^{\circ}\), czyli zamieńmy punkt każdy punkt z wejścia \((a, b)\) na punkt \((a+b, a-b)\). Dlaczego? Pierwsza intuicja wywodzi się z próby uproszczenia wzoru: zastanówmy się, kiedy \(\max(|x-x_i|,|y-y_i|) = |x-x_i|\). Okazuje się, że wykres wartości punktów dla których \(|x-x_i| \geq |y-y_i|\) po obróceniu o \(45^{\circ}\) będzie składał się z dwóch ćwiartek płaszczyzny, na których dużo łatwiej jest wykonywać różne operacje. Ponadto, możemy zauważyć, że dla dowolnych liczb rzeczywistych \(a, b\) zachodzi następująca równość: \(|a+b| + |a-b| = 2\max(|a|, |b|)\).

Po obrocie możemy zatem mierzyć odległość w metryce Manhattan zamiast w metryce maksimum, co jest o wiele wygodniejsze. Wówczas siła sygnału w punkcie \((x, y)\) względem \(i\)-tego przekaźnika będzie równa \(\max(0, s_i - \frac{|x-x_i| + |y-y_i|}{2})\). Następnie możemy zapomnieć o braniu większej wartości spośród 0 i różnicy. Nawet jeśli wtedy maksymalna siła sygnału dla pewnego zapytania okaże się ujemna, to na koniec zawsze możemy zwrócić 0. Ponadto możemy maksymalizować dwukrotność tego wyniku - to również nie zmienia optymalności. Zatem nasze zapytanie sprowadza się do znalezienia maksymalnej wartości wyrażenia \(2s_i - |x-x_i| - |y-y_i|\). Niech \(A\) będzie ograniczeniem górnym na wartość bezwzględną współrzędnych. By poradzić sobie z ujemnymi współrzędnymi, do wszystkich punktów dodajmy \(A\) (czyli przesuńmy całą płaszczyznę o wektor \((A, A)\)). Wówczas wszystkie współrzędne będą nieujemne, a wynik się nie zmieni.

Ponieważ wartość bezwzględna jest trudna do bezpośredniego liczenia, to również i tutaj będziemy czynić kolejne uproszenia. Jak to zrobić? Teraz możemy skorzystać z definicji wartości bezwzględnej, żeby uprościć powyższy wzór na cztery przypadki, w zależności od tego, w jakiej ćwiartce względem przekaźnika znajduje się zapytanie \((x, y)\). Załóżmy tymczasowo, że przekaźnik \(i\) emituje sygnał jedynie w górę-prawo. Wtedy podwojona siła sygnału w punkcie \((x, y)\) wynosi \(2s_i + x - x_i + y - y_i = (x+y) + (2s_i - x_i - y_i) \), przy czym oczywiście musi być spełnione \(x \geq x_i\) oraz \(y \geq y_i\) (czyli punkt \((x, y)\) musi odbierać sygnał emitowany w tym kierunku przez \(i\)-ty przekaźnik). Zatem dla tego zapytania chcemy znaleźć przekaźnik spełniający \(x_i \leq x\) oraz \(y_i \leq y\) i maksymalizujący wartość \(2s_i - x_i - y_i\).

Możemy zatem zastosować technikę zamiatania na płaszczyźnie, żeby znaleźć tę wartość. Posortujmy dane z wejścia najpierw względem drugiej współrzędnej, a następnie względem pierwszej niemalejąco. W przypadku remisów priorytetyzujemy przekaźniki nad zapytaniami. Następnie przeglądajmy punkty w takiej właśnie kolejności. Utrzymujmy jednocześnie drzewo przedziałowe rozpięte na przedziale indeksów \([0, A]\), początkowo wypełnione wartościami \(-\infty\). Jeśli trafimy na przekaźnik, to dodajmy wartość \(2s_i - x_i - y_i\) do drzewa przedziałowego w punkcie \(x_i\). Z kolei jeśli trafimy na zapytanie \((x_i', y_i')\), to zapytajmy drzewo przedziałowe o maksymalną wartość na przedziale \([0, x_i']\). Będzie to szukana maksymalna wartość \(2s_i - x_i - y_i\). Wówczas należy jeszcze uwzględnić składnik \(x_i'+y_i'\), aby otrzymać pełne wyrażenie, którego wartość maksymalizujemy. Dlaczego to działa? Ponieważ w momencie, gdy przetwarzamy zapytanie \((x_i', y_i')\), to wszystkie przekaźniki o współrzędnej \(x_i \leq x_i'\) oraz \(y_i \leq y_i'\) zostały już przetworzone (co wynika z posortowania danych w ten sposób), a zatem ich wartości \(s_i - x_i - y_i\) znajdują się w drzewie przedziałowym.

Analogicznie rozpatrzmy pozostałe trzy możliwe kierunki nadawania sygnału przez przekaźnik (góra-lewo, dół-prawo, dół-lewo). Możemy to zrealizować np. poprzez czterokrotne obrócenie całej płaszczyzny o \(90^{\circ}\), a następnie zastosowanie już powyżej opisanego algorytmu. Dla każdego zapytania znajdujemy zatem cztery maksymalne wartości sygnału z każdej ćwiartki względem punktu tego zapytania, z których wybieramy największą. Należy przy tym pamiętać, że w każdej chwili liczyliśmy dwukrotność faktycznej mocy sygnału, zatem wynik na końcu należy podzielić przez \(2\). Otrzymujemy rozwiązanie działające w czasie \(O((n+m)(\log(n+m)+\log(A)))\), co wynika z konieczności posortowania danych oraz zastosowania drzewa przedziałowego rozpiętego na przedziale indeksów rozmiaru \(O(A)\).

Pełne rozwiązanie – \(|x_i|, |y_i|, s_i, |x_i'|, |y_i'| \leq 10^{18}\)

Spróbujmy zoptymalizować rozwiązanie z poprzedniego podzadania. Jedynym problemem jest fakt, że współrzędne w tym podzadaniu są za duże, by móc je utrzymywać bezpośrednio na drzewie przedziałowym. Zauważmy jednak, że możemy zastosować technikę kompresji współrzędnych, by zmniejszyć zakres ich wartości. Wystarczy, że indeks współrzędnej \(x_i\) na drzewie przedziałowym będzie reprezentowany przez jej pozycję w posortowanej tablicy wszystkich współrzędnych \(x\)-owych. Wówczas wciąż możemy zastosować drzewo przedziałowe do znajdowania maksymalnej wartości na przedziale. Różnych wartości \(x_i, x_i'\) jest \(O(n+m)\), zatem zastosowanie powyższej kompresji pozwalało otrzymać wzorcowe rozwiązanie o złożoności \(O((n+m)\log(n+m))\).