[leoha]

Czy ktoś potrafiłby mi wytłumaczyć jak rozwiązać to zadanie https://www.hackerrank.com/challenges/direct-connections w czasie O(n*log(n)) np. używając Segment Tree? Tak, wiem można znaleźć gotowca na githubie, ale chciałbym zrozumieć w jaki sposób tutaj użyć tego drzewa (ew. drzew). W komentarzach jedna osoba zasugerowała posortowanie rosnąco po populacji i później iterując do wyniku dodawać kolejno iloczyn populacji i sumy odległości do poprzednich miast. Tyle, że nie wiem jak używając Segment Tree (albo jakiejkolwiek innej struktury) znaleźć tę rzeczoną sumę w O(log(n)).
Ktoś, coś?

#programowanie
#algorytmy

[s.....a]

@leoha: już czytam

[MasterSoundBlaster]

@slucham-psa-jak-gra:
Przeczytałeś i coś z tego wynikło? ( ͡° ͜ʖ ͡°)

[s.....a]

@MasterSoundBlaster: nie wynikło xd coś bym kombinował z posortowaniem i potem jakoś zliczaniem tego, ale nie chciało mi się myśleć ( ͡° ͜ʖ ͡°)