h2. Solutia 2

O prima observatie impotanta (defapt aceeasi ca observatia importanta de la problema Wiring de la IOI 2017) este aceea ca, pentru un interval de query $[l, r]$ fixat, va exista o pozitie $p$ unde toti copii din intervalul $[l, p]$ se dug "la stanga", si toti copii din intervalul $[p+1, r]$ se duc "la dreapta" (caci daca aceasta nu ar exista, ar fi un copil ce se duce "la stanga" care e mai la dreapta ca un copil ce se duce "la dreapta", care e evident neoptim).
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. Astfel, putem cauta ternar valoarea lui $p$ (avand in vedere cazul special de egalitate). Complexitatea finala este de $O(n * log(n))$.

///Tamio, please...

h2. Solutia 3