Analiza

Jasno je da je za svaki upit ~(A, B)~ potrebno izračunati vrednost izraza ~\sum_{i=1}^n \min(|x_i - A|, |x_i - B|)~ tj. sumu rastojanja do najbliže prodavnice. Direktno računanje ove sume za svaki upit daje rešenje složenosti ~O(nm)~ što je dovoljno samo za 20 poena.

Posmatrajmo slučaj kada uvek važi ~A_i = B_i~ tj. kada je potrebno izračunati ~\sum_{i=1}^n |x_i - A|~. Za početak, prirodan korak je sortiranje niza ~x~ -- nadalje pretpostavljamo da je ~x_1 \leq x_2 \leq \ldots \leq x_n~. Za datu vrednost ~A~ možemo binarnom pretragom u složenosti ~O(\log n)~ odrediti najveću vrednost ~ind~ za koju važi ~x_{ind} < A~ (ili ustanoviti da takva vrednost ne postoji ako je ~A \leq x_1~). Sada važi \sum_{i=1}^n |x_i - A| = \sum_{i = 1}^{ind} (A - x_i) + \sum_{i=ind+1}^n (x_i - A) = ind \cdot A - s_{ind} + (s_n - s_{ind}) - (n - ind)\cdot A gde je ~s~ niz prefiksnih suma niza ~x~, tj. ~s_i = x_1 + x_2 + \ldots + x_i~. Prema tome, ukoliko na početku (pre svih upita) sortiramo niz ~x~ i izračunamo niz prefiksnih suma, možemo za svaki upit odraditi binarnu pretragu i vratiti rezultat iz prethodne jednačine (bez sumiranja). Složenost ovog pristupa je ~O(n \log n + m \log n)~.

Prethodni algoritam se jednostavno modifikuje i u slučaju kada je ~A_i \neq B_i~. U tom slučaju, za upit ~(A, B)~ (npr. neka je ~A < B~) binarnom pretragom pronađemo najveću vrednost ~mid~ za koju važi ~x_{mid} < \frac{A+B}{2}~; to znači da će svi stanovnici sa koordinatama ~x_1, x_2, \ldots, x_{mid}~ ići u prodavnicu ~A~ a stanovnici sa koordinatama ~x_{mid+1}, x_{mid+2}, \ldots, x_n~ u prodavnicu ~B~. Zatim dva puta primenimo prethodni algoritam, jednom za podniz ~x[1, mid]~ i vrednost ~A~, a drugi put za podniz ~x[mid+1, n]~ i vrednost ~B~.

Za dodatne podzadatke je takođe predviđen ovaj algoritam ali je za njih dovoljna potencijalno lakša imeplementacija i manja analiza specijalnih slučajeva o kojima treba voditi računa prilikom implementacije rešenja za ~100~ poena -- npr. kada su vrednosti ~A~ ili ~B~ ili ~\frac{A+B}{2}~ levo ili desno od niza ~x~ (npr. kada svi idu u samo jednu prodavnicu). Ovo se u potpunosti može zaobići pametno dizajniranom funkcijom za pomenutu binarnu pretragu.