Malarz (mal): Re: Skalowanie przedziałów

Public message

Rzeczywiście, ta część nie jest jasna. Idea jest taka, że jak masz zakres jakiś <0,10^9> albo <0,10^18> to nie możesz go dać jako baza drzewa przedziałowego, oczywiście, bo jest za duży. Od teraz ten zakres będę nazywał R. Można jednak zauważyć, że zapytań z zadania będzie około 10^5-10^6. Te zapytania to pewnie pojedyncze lub podwójne indeksy (pary indeksów), więc łącznie różnych indeksów jest maksymalnie rzędu 10^6. Niech Q będzie zbiorem tych indeksów. Chcemy teraz wziąć każdy indeks z Q i przetłumaczyć ich wartości z R w zakres D = <0,~10^6>, żeby można je było zmieścić w drzewie przedziałowym. W tym celu sortujemy elementy Q (po wczytaniu wszystkich zapytań) i najmniejszemu przypisujemy 0, drugiemu najmniejszemu przypisujemy 1 itd. aż największemu indeksowi z Q przypiszemy liczbę rzędu 10^6 lub mniejszą. Stworzyliśmy tłumaczenie z R w D. Możemy je zapisać np. w std::map<> albo std::unordered_map<> Teraz, obsługujemy zapytania w oryginalnej kolejności. Gdy pojawia się jakiś indeks n, to zerkamy do słownika i wyłuskujemy jego odpowiednik w D. To jest tak jakbyśmy każdemu indeksowi z wejścia przypisali numerek z przedziału, który nam odpowiada w celu dalszej obsługi. Często konieczne będzie stworzenie tłumaczenia w drugą stronę. Tzn. w momencie gdy tworzymy tłumaczenie z R w D, to za każdym razem, gdy przypisujemy jakiemuś elementowi w R jakiś element w D, to tworzymy również przypisanie odwrotne, z D w R, w drugiej mapie, hashmapie, lub tym razem tablicy. To jest szczególnie przydatne gdy w zadaniu gra rolę długość przedziału. Nie możemy wówczas korzystać z róznicy indeksów wierzchołków w drzewie przedziałowym, tylko musimy korzystać z róznic oryginalnych wartości. Lub gdy musimy zwrócić indeks wierzchołka, dla którego osiągane jest np. maksimum -- wówczas indeks w drzewie przedziałowym nie będzie jego "prawdziwym", by tak rzec, indeksem. Możliwość utworzenia tłumaczenia odwrotnego wynika stąd, że tłumaczenie pierwotne jest różnowartościowe. Mam nadzieję, że rozjaśniłem sprawę. :3