Fişierul intrare/ieşire:	eq.in, eq.out	Sursă	Autumn Warmup 2006
Autor	Vlad Berteanu	Adăugată de
Timp execuţie pe test	0.425 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Easy Query

Easy Query

Se considera un sir de N numere naturale, x¹, x², ... 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.

Cerinta

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

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.

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.

Restrictii si precizari

o 1 < N <= 100 001
o 1 < M <= 130 001
o 0 <= x[i] <= 2^24

Exemplu

Cum se trimit solutii?