Pomysł na algorytm w zadaniu Biblioteka

Witam, dostałem niedawno do rozwiązania zadanie Biblioteka. Niestety nie mam w ogóle pomysłu na algorytm. Zapytałem się nauczyciela o jakąkolwiek wskazówkę a on podpowiedział, żeby skorzystać z drzewa binarnego i z *(odnośnik na dole). To drugie umiem robić, ale nadal nie wiem jak wykorzystać drzewo w tym zadaniu. Oczywiście można byłoby zrobić to zadanie iteracyjnie (tzn. w pętli od prawej strony przeglądać pierwszy mniejszy element a potem od tego elementu kolejna pętla) ale nauczyciel powiedział, że to rozwiązanie nie przejdzie 70% testów ze względu na czas. Ma ktoś pomysł na algorytm?

• Nie wiem jak nazywa się ta sztuczka, ale chodzi o to, aby zmniejszyć wartości ciągu zachowując przy tym zależności między nimi (np. dla ciągu 2 100 3 4 można byłoby go przekształcić na ciąg: 1 4 2 3 i zależności między poszczególnymi elementami zostałyby zachowane, np. drugi element jest nadal większy od pozostałych).

Link do zadania: bib.pdf

Rozwiazanie ktore widze wydaje sie byc zbyt pracochlonne do napisania wiec pewnie da sie jakos prosciej, ale rzeczywiscie da sie to zrobic na drzewie. Nie zamierzam podawac dokladnego rozwiazania pracy domowej (zreszta nawet nie przeanalizowalem wszystkich warunkow, wiec jest niezerowe prawdopodobiensto ze cos przeoczylem. ale raczej nie, i mimo ze duzo pracy, to koncepcyjnie raczej nie jest przesadnie skomplikowane), ale moge dac kilka wskazowek:

1. W rozwiazaniu ktore widze niezbedny jest dostep do dzieci i rodzica. Nie kojarze nic takiego w standardzie, wiec jesli rzeczywiscie nie ma, i nie mozesz korzystac z bibliotek, to trzeba samemu napisac rownowazenie drzewa.
2. W kazdym wezle trzeba przechowywac dodatkowe informacje. Sam wymysl jakie, ale to wydaje sie byc oczywiste. Przy dodawaniu nowego wezla trzeba odswiezac informacje tez w innych wezlach. Wystarczy to zrobic na sciezce korzen - wezel (pamietajac ze wartosci beda sie zmienialy przy rownowazeniu drzewa).
3. Algorytm powinien zajac O(nlogn) - pojedyncze przejscie przez dane w trakcie ktorego budowane jest drzewo, zapamietywane sa odpowiednie wartosci w wezlach, i kumulowany jest wynik koncowy.
4. Kompletnie nie widze potrzeby korzystania z "*(odnośnik na dole)" (ale moze to jest jakas wskazowka jak sie nie narobic przy implementacji np. drzewa czerwono czarnego).
5. Proponuje zaczac od zrobienia tego zadania dla 2 ksiazek. Dodanie trzeciej to ciagle ten sam algorytm, tylko troche bardziej skomplikowane obliczenia.

ps.
Uroczy jest kontrast miedzy burzliwa dyskusja bo w tym watku dotyczacym zadania licealnego, a np. watkiem na kilkaset stron dotyczacym zarobkow, gdzie panuje powszechna opinia ze programista nie powinien sie znizac do pracy za mniej niz kilkukrotnosc sredniej krajowej.