Oare putem, pentru un interval $[l, r]$, si o pozitie $p$ in acest interval, sa gasim "repede" care ar fi costul daca toti copii din $[l, p]$ ar merge "la stanga", si toti copii din $[p+1, r]$ sa mearga "la dreapta"? Sa numim aceasta valoare f(l, r, p).
Raspunsul este da: f(l, r, p) este egala cu suma pozitiilor copiilor din $[l, p]$ minus suma pozitiilor copiilor din $[p+1, r]$, plus suma indicilor primilor $(nr. copii din [p+1, r])$ spatii goale din dreapta lui $r$, minus suma indicilor ultimilor $(nr. copii din [l, p])$ spatii goale din stanga lui $l$. Toate valorile mentionate pot fi gasite in $O(1)$ cu ajutorul unor precalculari usoare in $O(n)$.
Acum, cum gasim acea pozitie optima a lui $p$ ?
Observatia importanta este ca functia $g(p) = f(l, r, pozitia celui de al p-lea copil din [l, r])$ este "aproape" unimodala ; mai exact, aceasta poate avea $2$ minime, dar acestea trebuie atunci sa fie adiacente. Mai mult, observam oricare valori egale in $p$ trebuie sa fie una in stanga si una in dreapta minimului. Pentru a demonstra acest lucru, este nevoie sa observam ca, cat timp cuplam copii care merg la stanga (respectiv la dreapta) cu pozitiile goale cele mai la dreapta (respectiv la stanga) care sunt la stanga (respectiv la dreapta) lui $[l, r]$, putem cupla oricare copil cu oricare spatiu (din comutativitate); iar astfel, arbitrar, putem alege sa cuplam al $i$-lea copil de la stanga (respectiv la dreapta) lui $[l, r]$ cu al $i$-lea copil de la dreapta la stanga (respectiv de la stanga la dreapta) la stanga (respectiv la dreapta) lui $[l, r]$. Astfel, putem cauta ternar valoarea lui $p$ (avand in vedere cazul special de egalitate). Complexitatea finala este de $O(n * log(n))$.
Observatia importanta este ca functia $g(p) = f(l, r, pozitia celui de al p-lea copil din [l, r])$ este "aproape" unimodala ; mai exact, aceasta poate avea $2$ minime, dar acestea trebuie atunci sa fie adiacente. Mai mult, observam oricare valori egale in $p$ trebuie sa fie una in stanga si una in dreapta minimului. Astfel, putem cauta ternar valoarea lui $p$ (avand in vedere cazul special de egalitate). Complexitatea finala este de $O(n * log(n))$.
h2. Solutia 3
