Easy Query

eq

==Include(page="template/taskheader" task_id="eq")==

== include(page="template/taskheader" task_id="eq") ==

Se considera un sir de $N$ numere naturale, {$x{~1~}, x{~2~}, ... x{~N~}$}. Se defineste urmatoarea operatie:
 
* pentru o pereche {$i,j$}, {$1 ≤ i ≤ j ≤ N$}, se considera secventa {$x{~i~}, x{~i+1~}, ... x{~j~}$}
* se construiesc doua siruri corespunzatoare secventei date, astfel:
** {$y{~t~} = x{~t~} - x{~k~} + x{~p~}$}, {$i ≤ t ≤ j$}, {$t ≤ k ≤ j$}, {$t ≤ p ≤ j$}, unde $y{~t~}$ este maxim
** {$z{~t~} = x{~t~} - x{~k~} + x{~p~}$}, {$i ≤ t ≤ j$}, {$t ≤ k ≤ j$}, {$t ≤ p ≤ j$}, unde $z{~t~}$ este minim
* se calculeaza valoarea {$P = max(y) + min(z)$}, unde $max(y)$ este maximul din sirul $y$ construit ca mai sus, iar {$min(z)$} minimul din sirul {$z$}.

Poveste ...

h2. Cerinta

Dandu-se sirul initial, sa se raspunda la un set de mai multe operatii.

...

h2. Date de Intrare

h2. Restrictii

Pe prima linie a fisierului de intrare $eq.in$ se gasesc doua numere $N$ si $M$ reprezentand numarul de elemente ale sirului {$x$}, respectiv numarul operatiilor pentru care se doreste determinarea valorii {$P$}. Pe urmatoarea linie se afla elementele sirului $x$ separate prin cate un caracter spatiu. Urmatoarele $M$ linii contin subsecventele definite prin doi intregi $i$ si $j$ separati prin spatiu reprezentand pozitia de inceput, respective pozitia de sfarsit a subsecventei.

...

h2. Date de Iesire

h2. Date de intrare

Fisierul de iesire $eq.out$ contine valorile P pentru fiecare subsecventa data, cate una pe linie, in ordinea aparitiei acestora in fisierul de intrare.

...

h2. Restrictii si precizari

h2. Date de iesire

* $1 < N &le; 100 001$
* $1 < M &le; 130 001$
* $0 &le; x{~i~} &le; 2^24^$

...

h2. Exemplu

table(example). |_. eq.in |_. eq.out |
| 6 3
1 8 10 5 9 3
1 4
2 6
3 5
| 7
16
16 |
 
 

| eq.in | eq.out |
| linia1
linia2
linia3
| linia1
linia2
|

==Include(page="template/taskfooter" task_id="eq")==
 
 

== include(page="template/taskfooter" task_id="eq") ==

1229