Re: Bokserzy [Runda 20] - rozwiązanie
Moje rozwiązanie:
Mamy sobie strukturę
Jest to drzewo, które w w[1] trzyma całą tablicę, w w[2] trzyma pierwszą połowę, w w[3] drugą połowę, w w[4] pierwszą ćwiartkę itd. i to wszystko posortowane. Ma to zapewne jakąś nazwę, ale jej nie znam.
Mając taką strukturę, możemy na każde zapytanie odpowiedzieć w O(log^2n) - dla każdego jak największego przedziału zawartego w zadanym * używamy wyszukiwania binarnego.
* czyli np. dla (4,9) przeglądamy (4,7) i (8,9)
Zalążek rozwiązania, na które wpadłem później:
Trzymać posortowane początki przedziałów z zapytań. Przeglądnąć po kolei wszystkich zawodników. Jeśli natrafiamy na początek jakiegoś przedziału, to dla tego zapytania (którego początkiem jest ten, przy którym jesteśmy) zapisujemy ilość remisujących i przegrywających do tego miejsca. To samo z końcami tyle że idąc od tyłu. Jak to zrealizować (to znajdowanie wyników - ilości remisujących i przegrywających)? Nie wiem. Pewnie drzewko jakieś, set może. Nie zastanawiałem się nad tym.
PS.: Może wrzucajmy pytania o rozwiązania zadań w dziale "ciekawe rozwiązania". Może i nie zawsze rozwiązanie będzie "ciekawe", ale zwiększy to porządek na forum - chyba lepiej mieć wszystkie opisy rozwiązań w jednym miejscu.