h2. easy query
Un algoritm simplu de complexitate $O(N*M)$ obtine $30-50$ de puncte. Algoritmul de $100$ de puncte are complexitatea $O(MlogN)$ si foloseste arbori de intervale. Considerand o secventa $x{~i~} x{~i+1~}... x{~j~}$ este evident ca pentru ca elementele sirurilor $y$ si $z$ sa fie maxime, respectiv minime, ele trebuiesc construite astfel:

$y{~t~} = x{~t~}- min(x{~k~}) + max({~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
$z{~t~} = x{~t~} - max(x{~k~}) + min({~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$

 
* $y{~t~} = x{~t~}- min(x{~k~}) + max(x{~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
* $z{~t~} = x{~t~} - max(x{~k~}) + min(x{~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
 

Pentru a calcula in timp optim valoarea $P = max(y) + min(z)$ ne vom folosi de un arbore de intervale in urmatorul mod: fiecare nod al acestuia va constitui o secventa $x{~st~}, x{~st+1~}... x{~dr~}$ ( unde $st$ si $dr$ sunt marginile intervalului din nodul arborelui ) pe care o vom rezolva prin metoda brute force de la inceput, avand grija sa precalculam si alte valori necesare mai tarziu, cum ar fi :

$min = minim(x{~st~}, x{~st+1~}... x{~dr~})$
$max = maxim(x{~st~}, x{~st+1~}... x{~dr~})$
$x_max_max = maxim(x{~t~} + maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
$x_max_min = minim(x{~t~} - maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
$x_min_max = maxim(x{~t~} - minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
$x_min_min = minim(x{~t~} + minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
$y_max = maximul din sirul y corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$
$z_min = minimul din sirul z corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$

 
* $min = minim(x{~st~}, x{~st+1~}... x{~dr~})$
* $max = maxim(x{~st~}, x{~st+1~}... x{~dr~})$
* $x_max_max = maxim(x{~t~} + maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_max_min = minim(x{~t~} - maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_min_max = maxim(x{~t~} - minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_min_min = minim(x{~t~} + minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $y_max = maximul din sirul y corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$
* $z_min = minimul din sirul z corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$
 

Avand precalculate valorile de mai sus pentru fiecare nod al arborelui in parte vom putea raspunde in timp $O(logN)$ pentru fiecare din cele $M$ intrebari. Fiecare subsecventa data $x{~i~}, x{~i+1~}... x{~j~}$ va putea fi compusa din reuniunea mai multor noduri din arborele de intervale. Acum parcurgem nodurile ce compun subsecventa data de la dreapta la stanga si vom gasi rapid valorile $maxim(y)$ si $minim(z)$. Presupunand ca am ajuns la nodul $Q$ valoarea $maxim(y)$ pana aici se calculeaza astfel:

@MAX(Y) = y_max(Q) = y_max_max(Q) - min(W) = x_min_max(Q)+max(W) = max(Q)+max(W)-min(W)@

 
* @MAX(Y) = y_max(Q) = y_max_max(Q) - min(W) = x_min_max(Q)+max(W) = max(Q)+max(W)-min(W)@
 

Analog se calculeaza si $minim(z)$.