Omówienie zadania Wyścigi (III etap XXVI OI)

Dla uproszczenia analizy zadania możemy posortować ciąg wejściowy, czyli założyć, że wyniki punktowe zawodników spełniają \(p_1 \le p_2 \le \ldots \le p_n\). Ponieważ w odpowiedzi interesuje nas tylko liczba zawodników, a nie ich numery, więc podczas implementacji możemy po prostu posortować ciąg \(p_i\).

Podzadanie 1

Najpierw rozwiążmy zadanie, w którym musimy tylko odpowiedzieć raz na zapytanie, ilu zawodników może jeszcze wygrać zawody.

Kiedy \(i\)-ty kierowca może wygrać? Wystarczy sprawdzić, czy wygrywa mistrzostwa, gdy w finałowym wyścigu zajmie pierwsze miejsce (aby dostał jak najwięcej punktów), a ostatnie \(n-i\) miejsc zajmą zawodnicy z numerami kolejno \(i+1, i+2, \dots, n\) (aby zawodnicy, którzy mu najbardziej zagrażają dostali jak najmniej). Formalnie, wystarczy sprawdzić warunek \[p_i + n \ge \max_{i< j \leq n} (p_{j} + n+1-j).\]

Można udowodnić, że jeśli \(i\)-ty zawodnik może wygrać mistrzostwa, to wygrywa je, gdy kolejność w ostatnim wyścigu jest \(i, n, n - 1, \ldots, i + 1, i - 1, \ldots, 2, 1\).

Dla dowodu załóżmy, że mamy pewną permutację zawodników po której \(i\)-ty kierowca wygrywa mistrzostwa. Zauważmy, że bez straty ogólności może wygrać ostatni wyścig, bo jeśli zdobył mistrzostwo nie wygrywając, to na pewno może je zdobyć wygrywając ostatni wyścig (zdobędzie jeszcze więcej punktów).

Dalej kierowcy o numerach \(j < i\) mogli zdobyć w ostatnim wyścigu co najwyżej \(n - 1\) punktów, a jako że \(p_j \le p_i\), więc nie stanowią żadnego zagrożenia dla \(i\)-tego zawodnika. Tak więc możemy ich przestawić w naszej permutacji o dowolną liczbę miejsc w lewo (ale nie dalej niż na drugą pozycję), więc przestawiamy ich na pozycje \(2, 3, \ldots, i\).

Stąd wynika, że możemy założyć, że zawodnicy o numerach \(i + 1, \ldots, n\) są w permutacji na pozycjach \(i + 1, \ldots, n\). Wystarczy już tylko pokazać, że jeśli tacy dwaj zawodnicy \(j_1 < j_2 \in \{i + 1, \ldots, n\}\) są w permutacji na pozycjach odpowiednio \(l_1 > l_2\), to możemy zamienić ich miejscami. Przeliczmy to: z tego, że kierowca o numerze \(i\) wygrał mistrzostwo wynika, że \[p_i + n \ge p_{j_1} + (n - l_1 + 1),\] \[p_i + n \ge p_{j_2} + (n - l_2 + 1).\] Stąd wynika, że \[p_i + n \ge p_{j_2} + (n - l_2 + 1) \stackrel{p_{j_2} \ge p_{j_1}}{\ge} p_{j_1} + (n - l_2 + 1),\] \[p_i + n \ge p_{j_2} + (n - l_2 + 1) \stackrel{-l_2 > -l_1}{>} p_{j_2} + (n - l_1 + 1).\] Zatem możemy zamieniać takie pary w permutacji miejscami. Stąd wynika teza.

Dla ustalonego \(i\) warunek na wygrywanie możemy wyliczyć w czasie \(O(n)\). Jeśli zrobimy to niezależnie dla każdego z \(n\) kierowców, to złożoność takiego rozwiązania będzie \(O(n^2)\).

Podzadanie 2

Nietrudno jednak przyspieszyć ten algorytm, zauważając, że maksima, które będziemy wyliczać w warunku, dotyczą zawsze sufiksu ciągu. Możemy zatem iterować się po zawodnikach od strony prawej do lewej i na bieżąco wyznaczać sobie aktualne maksimum. Wtedy wyznaczenie maksimum dla kolejnego kandydata będziemy mieli w czasie stałym, więc sumarycznie całe przejście po tablicy zrobimy w czasie \(O(n)\). Dodając do tego początkowe sortowanie zawodników, dostajemy algorytm o złożoności \(O(n \log n)\).

Ponieważ podczas analizowania kolejnych kandydatów lewa strona warunku nie rośnie, a prawa nie maleje, więc zawodnicy, którzy mogą wygrać, stanowią sufiks ciągu.

Podzadanie 3

Powyższy algorytm stanowi podstawę rozwiązania podzadania 3. Kary i bonusy możemy rozpatrywać brutalnie, po prostu przechodząc cały ciąg i odpowiednio zmieniając wyniki punktowe wszystkich zawodników, a następnie na nowo je sortując. Tak więc każde zapytanie zrealizujemy w czasie \(O(n\log n)\), a całe zadanie w czasie \(O(qn\log n)\).

Pełne rozwiązanie

Zauważmy, że bonus zawsze będzie zmieniał wartości na pewnym sufiksie ciągu, a kara zawsze będzie zmieniała wartości na pewnym prefiksie ciągu. Wynika też z tego, że kary i bonusy nie zmieniają kolejności kierowców w posortowanym ciągu (po zastosowaniu bonusu na posortowanym ciągu ciąg pozostaje posortowany).

Zauważmy jeszcze, że wystarczy umieć obsługiwać tylko zapytania typu bonus. Gdy mamy zapytanie typu kara (wszystkim kierowcom, którzy mają co najwyżej \(x_i\) zabieramy \(y_i\) punktów), to zamiast dawać karę, możemy dać bonus o wielkości \(y_i\) wszystkim kierowcom, którzy mają przynajmniej \(x_i + 1\) punktów, i dodatkowo pamiętać, że wszystkie wartości ciągu zostały sztucznie zwiększone o \(y_i\).

Do utrzymywania ciągu możemy wykorzystać drzewo przedziałowe, które udostępnia możliwość dodania lub odjęcia liczby na przedziale. Każda taka operacja będzie działała w czasie \(O(\log n)\), a po szczegóły implementacyjne odsyłamy do książki Przygody Bajtazara.

Pozostaje zatem zastanowić się, jak wykorzystać to drzewo do odpowiadania na pytania o liczbę zwycięzców, czyli jak za jego pomocą sprawdzać warunek. W tym warunku musimy umieć obliczać maksima na pewnych sufiksach, czyli tak naprawdę maksima na pewnych przedziałach w naszym drzewie (i to jest typowym przykładem drzewa typu przedział-przedział). Problematyczne jest jednak to, że taki warunek musimy obliczyć dla każdego zawodnika, czyli w sumie musimy porównać \(n\) takich przedziałów z maksimum.

Ale możemy nasz warunek uprościć. Zauważmy, że sprawdzamy w nim wyniki zawodników o indeksach większych niż \(i\), ponieważ powiedzieliśmy, że są to jedyni zawodnicy, którzy mogą zagrozić zawodnikowi \(i\)-temu. Wynika to z tego, że niezależnie od tego, ile punktów zdobędą zawodnicy o mniejszych numerach, nadal będą mieli mniej punktów niż \(i\)-ty zawodnik. Ale to oznacza, że możemy rozszerzyć to maksimum o obliczanie go dla wszystkich zawodników i nie zmieni to w żaden sposób wyniku. \[p_i + n \ge \max_{1\leq j \leq n} (p_{j} + n+1-j).\]

Czyli będziemy odpytywali się jedynie o maksimum na całym przedziale i jeżeli oznaczymy to maksimum przez \(M\), to nasz warunek jest równoważny temu, że \(p_i \geq M - n\). Ponieważ liczba \(M-n\) będzie stała dla wszystkich zawodników, tak więc aby wyznaczyć liczbę wszystkich zwycięzców zawodów, musimy odpowiedzieć na pytanie, ile jest takich liczb \(p_i\), które są większe równe \(M - n\). A to również możemy w prosty sposób wyszukiwaniem binarnym znaleźć w drzewie przedziałowym w czasie \(O(\log n)\).

Podsumowując, będziemy utrzymywać dwa drzewa przedziałowe:

• W jednym będziemy trzymać wartości \(p_i\), po to żeby móc odpowiadać na zapytanie, ile jest aktualnie wartości \(p_i\) większych równych od ustalonej liczby.

• W drugim będziemy trzymać wartości \(p_i + n + 1 - i\), po to żeby móc szybko wyznaczać maksimum spośród wszystkich tych wartości.

W przypadku bonusu będziemy uaktualniać oba te drzewa.

Ostatecznie złożoność czasowa naszego programu to będzie \(O(n\log n + q \log n)\).