==Include(page="template/taskheader" task_id="eq")==
==Include(page="template/raw")==
Easy Query
Se considera un sir de N numere naturale, x[1], x[2], ... x[n]. Se defineste urmatoarea operatie:
- pentru o pereche (i, j), 0 < 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.
h2. Cerinta
Dandu-se sirul initial, sa se raspunda la un set de mai multe operatii.
h2. Date de Intrare
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
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
o 1 < N <= 100 001
o 1 < M <= 130 001
o 0 <= x[i] <= 2^24
h2. Exemplu
|eq.in |eq.out |
|6 3 |7 |
| | |
|1 8 10 5 9 3 |16 |
| | |
|1 4 |16 |
| | |
|2 6 | |
| | |
|3 5 | |
==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$}.
h2. Cerinta
Dandu-se sirul initial, sa se raspunda la un set de mai multe operatii.
h2. Date de Intrare
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
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
* $1 < N ≤ 100 001$
* $1 < M ≤ 130 001$
* $0 ≤ x{~i~} ≤ 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 |
==Include(page="template/taskfooter" task_id="eq")==
==Include(page="template/taskfooter" task_id="eq")==
