Zadanie z konkursu Potyczki Algorytmiczne

Prośba o pomoc. Czy ktoś byłby tak miły i wytłumaczył jak rozwiązać zadanie Mopadulo z ostatnich potyczek algorytmicznych?
Treść zadania jest dostępna tutaj:
https://sio2.mimuw.edu.pl/c/pa-2021-1/p/mop/
Jest też opisane rozwiązanie, a właściwie koncepcja rozwiązania (strona nr 12):
https://sio2.mimuw.edu.pl/c/pa-2021-1/ca/305/

Doszedłem do tego jak to zrobić za pomocą DP ze złożonością O(N^2).
Wiem jak działa drzewo potęgowe Fenwicka i że pozwala na aktualizację i odczytywanie sum prefiksowych w złożoności O(log N).
Niestety, nie bardzo wiem jak to zastosować w tym przypadku. Nie rozumiem o jakie przeskalowanie chodzi, jakie sumy parzyste i nieparzyste trzeba zliczać.
Byłbym wdzięczny za bardziej szczegółowy opis rozwiązania, najlepiej na przykładzie.
Może przeczyta to ktoś, kto rozwiązał to zadanie na konkursie i podzieli się doświadczeniem?

W przeskalowaniu chodzi o to, że nie budujesz drzewa na dowolnych wartościach z zakresu 0-300000 \times 1000000007, tylko wyliczasz po kolei sumy prefiksowe, numerujesz je i dostajesz jakieś k różnych sum, a następnie robisz drzewo na przedziale 1-k.

Przykład: masz elementy 1, 3, 5, 100000.
Liczysz sumy prefiksowe: 1, 4, 9, 100009.
Teraz musiałbyś zrobić drzewo przedziałowe na zakresie 1-100009 i wstawić jedynki w odpowiednie miejsca. Ale przeskalowujesz:
1 = 1, 2 = 4, 3 = 9, 4 = 100009. Teraz robisz drzewo na przedziale 1-4.
I jak chcesz szukać tych wszystkich prefiksów mniejszych lub równych jakiemuś x, to najpierw przeskalowujesz x tym słownikiem, dostajesz numer elementu i wtedy robisz podzapytanie do drzewa o odpowiedni zakres.
Teraz interesuje Cię tylko parzystość, więc możesz na przykład wzbogacić drzewo przedziałowe o zliczanie węzłów o zadanej parzystości w podprzedziałach, albo w ogóle możesz zignorować drzewo i znowu kombinować z sumami prefiksowymi elementów modulo dwa (chociaż drzewo prostsze), albo wstawiasz do drzewa sprytne wartości (na przykład 0.5 dla liczby nieparzystej, a 1 dla liczby parzystej, gdy chcesz zliczać parzyste sumy). Robisz to dwa razy, bo raz interesuje Cię suma parzysta, a raz nieparzysta.

Wróciłem po czasie do problemu. Po kolejnej dogłębnej analizie treści rozwiązania oraz podpierając się kodami rozwiązań (dostępne na stronie konkursu) udało mi się odgadnąć koncepcję rozwiązania. Jedna sprawa, która mi zawsze umykała to taka, że do przeskalowania używana jest posortowana lista prefiksów, co ma tutaj duże znaczenie.