Omówienie zadania Przekaźniki telekomunikacyjne (II etap XXV OI)

Pierwsze podzadanie

Proces zmiany sił sygnału w poszczególnych punktach jest prosty do symulowania, stąd naturalnym wydaje się pomysł utrzymywania siły sygnału w każdym momencie.

Dla każdego zapytania dodającego/usuwającego przekaźnik iterujemy się w obie strony i zmieniamy zapisaną siłę sygnału w punktach według wzoru z treści. Złożoność obsługi każdego dodania lub usunięcia przekaźnika to \(O(n)\)

Dla zapytania o średnią siłę sygnału na przedziale \([l, r]\) wystarczy podzielić sumę sił sygnałów przez ilość punktów. Ponieważ wiedzę o sile sygnału w każdym punkcie utrzymujemy na bieżąco, to wynik możemy obliczyć w czasie proporcjonalnym do długości przedziału, zatem w \(O(n)\)

W ten sposób otrzymujemy rozwiązanie w złożoności \(O(nm)\), którego implementację można znaleźć w pliku tels2.cpp.

Drugie podzadanie

Podstawowym faktem dotyczącym ciągów arytmetycznych, którego użyjemy w rozwiązywaniu pozostałych podzadań, jest fakt, że dla ciągów \(A: a_i\) i \(B: b_i\) ciąg \(C: c_i = a_i + b_i\) również jest ciągiem arytmetycznym. Ponadto jeśli ciąg A miał parametry \((s_a, d_a)\), a ciąg B miał parametry \((s_b, d_b)\) to ciąg C będzie opisany parametrami \((s_a + s_b, d_a + d_b)\). Dowód tego prostego faktu pozostawiam jako ćwiczenie dla czytelnika.

Wykorzystajmy fakt, że na początku podane są informacje dotyczące wszystkich przekaźników, a dopiero następnie mamy odpowiadać na zapytania. Podzielmy program na dwie części:

1. Stworzenie tablicy, która dla każdego punktu przechowuje siłę sygnału w tym punkcie.
2. Odpowiedzi na zapytania (o sumę siły sygnałów na przedziale).

Po stworzeniu tablicy z siłami sygnałów odpowiedzi można udzielać za pomocą sum prefiksowych w złożoności \(O(1)\) na jedno zapytanie. Skupmy się więc na tym, w jaki sposób efektywnie utworzyć taką tablicę.

Dodanie lub odjęcie przekaźnika telekomunikacyjnego jest równoznaczne z dodaniem odpowiedniego ciągu arytmetycznego na przedziale, wyznaczonym przez parametry \(s\) i \(a\).

Mianowicie, dla przekaźnika o parametrach \(x, s, a\). Musimy nanieść ciągi arytmetyczne:

• na przedziale \([x - \lfloor s/a \rfloor, x]\) dodać musimy ciąg, o kroku \(a\) i wyrazie końcowym \(s\), z czego wynika wyraz początkowy \(s_0 = s - \lfloor s/a \rfloor * a\)
• na przedziale \([x+1, x + \lfloor s/a \rfloor]\) dodać musimy ciąg, o kroku \(a\) i wyrazie początkowym \(s - a\).

Konstrukcję tablicy z siłami sygnałów zrealizujemy za pomocą zamiatania. Każdy początek i koniec ciągów z wejścia zaznaczymy w odpowiednich komórkach tablicy pomocniczej. W ten sposób, dla każdego punktu otrzymujemy ciąg będący sumą wszystkich ciągów które zaczynają się w tym punkcie, oraz z minusami dla tych, które kończą się w tym punkcie. Przechodząc tą tablicę od lewej do prawej, będziemy utrzymywać aktualne parametry ciągu arytmetycznego, który aktualizujemy korzystając z faktu o dodawaniu ciągów arytmetycznych. Złożoność takiego rozwiązania to \(O(n + m)\)

Trzecie podzadanie

Ułatwienie polegające na ograniczeniu liczby aktywnych przekaźników w jednym momencie zezwala na rozwiązanie, które odpowiada na zapytanie poprzez przejrzenie wszystkich aktywnych przekaźników. W tym celu potrzebujemy struktury danych, która pozwoli nam przechowywać i dodawać oraz usuwać przekaźniki (jako trójki liczb z wejścia) oraz iterować się po nich przy napotkaniu zapytania. Odpowiednią strukturą będzie np. unordered_map z biblioteki standardowej C++.

Aby odpowiedzieć na zapytanie iterujemy się po aktywnych przekaźnikach i dla każdego z nich obliczamy przedział będący przecięciem przedziałów zapytania oraz działania przekaźnika. Następnie przy pomocy prostych działań na ciągach arytmetycznych można policzyć sumę sił sygnałów w takim przedziale. Wyniki dla pojedyńczych przekaźników sumujemy, a następnie zwracamy jako wynik zapytania. Takie rozwiązanie zadziała w czasie \(O(m \cdot |p|)\), gdzie \(|p|\) to maksymalna liczba aktywnych przekaźników w jednym momencie i będzie wystarczające do przejścia trzeciego podzadania.

Piąte podzadanie

Do rozwiązania piątego podzadania użyjemy połączenia podejść rozwiązujących drugie i trzecie podzadanie, eliminując ich słabości, a łącząc ich zalety. Słabością podejścia zaproponowanego do podzadania drugi czas potrzebny na konstrukcję potrzebnych nam struktur, zaletą zaś jest szybkość odpowiedzi na zapytania. Zaletą podejścia opisanego w podzadaniu trzecim jest szybkość wprowadzania zmian w strukturze, wadą zaś długi czas odpowiedzi na zapytanie, jeśli dużo przekaźników jest aktywnych.

Możemy połączyć oba te podejścia, utrzymując w strukturze z podzadania 3 jedynie \(O (\sqrt{m})\) przekaźników. W momencie, gdy przekroczymy tą liczbę, zbudujemy z aktywntch przekaźników strukturę z podzadania 2 w czasie \(O(n + m)\). Zauważmy, że zrobimy to co najwyżej \(O(\sqrt{m})\) razy, więc złożoność czasowa tego kroku to \(O(\sqrt{m} \cdot (n + m))\). Wynikiem takiego hybrydowego podejścia będzie rozwiązanie, które działa w czasie \(O((n+m) \cdot \sqrt{m} + m \sqrt{m})\). Implementację tego rozwiązania można przeczytać w pliku tels3.cpp.

Pełne rozwiązanie

W pełnym rozwiązaniu potrzebujemy struktury bardziej elastycznej, która pozwoli dodawać na przedziale ciągi arytmetyczne, a także pytać o sumę wartości na wybranym przedziale. Oba te cele można osiągnąć za pomocą wzbogaconego drzewa przedziałowego.

Dla każdego przedziału bazowego będziemy utrzymywać informację \((s, d)\) o ciągu arytmetycznym, który pokrywa go w całości, co oznacza że \(i\)-ty element spośród \(2^{k}\) elementów w przedziale ma wkład równy \(s + (i-1) \cdot d\).

Aby dodać ciąg arytmetyczny o parametrach \((s, d)\) na przedziale \([l, r]\) znajdziemy rozkład przedziału na przedziały bazowe i dodamy do nich odpowiednie wartości. Do przedziału bazowego pokrywającego punkty \(l_i\) i \(r_i\) dodamy ciąg arytmetyczny o parametrach \((s + (l_i - l) \cdot d, d)\). Do uzyskania odpowiedzi na zapytanie ponownie znajdziemy przedziały bazowe i odczytamy z nich sumę ciągu z wzoru na sumę ciągu arytmetycznego.

Operacja zepchnięcia informacji o ciągu z przedziału do jego dzieci również możemy wykonać w prosty sposób: dla ciągu \((s, d)\) w wierzchołku rozmiaru \(2^{k-1}\) w lewym synie dodamy ciąg \((s, d)\), a w prawym ciąg \((s + d \cdot 2^{k-1}, d)\).

Wykonywanie każdej z tych operacji na drzewie zajmuje \(O(\log n)\) czasu, więc złożoność czasowa całego rozwiązania to \(O((n + m) \log n)\).