==Include(page="template/taskheader" task_id="sequencequery")==
 
==Include(page="template/raw")==
 
Sequencequery
 
 
 
 
 
Se considera un sir A = (a[1], a[2], ... , a[N]) format din N numere intregi, precum si M perechi de numere ( x, y ). Pentru fiecare pereche de indici (x, y) (1 <= x <= y <= N) trebuie determinata subsecventa de suma maxima a subsirului a[x], a[x+1], ..., a[y] .
 
h2. Date de Intrare
 
Fisierul sequencequery.in va contine pe prima linie doua numere intregi N si M . Urmatoarea linie va contine N numere intregi separate prin cate un spatiu. Acestea vor reprezenta numerele a[1], a[2], ... , a[N] . Urmatoarele M linii vor contine fiecare cate o pereche de doua numere separate prin cate un spatiu. Acestea vor indica perechile de indici pentru care trebuie determinate sumele maxime ale subsecventelor.
 
h2. Date de Iesire
 
Fisierul sequencequery.out va contine M linii. Fiecare dintre acestea va contine cate un numar intreg care reprezinta suma elementelor din subsecventa considerata optima dupa criteriile exprimate in enuntul problemei.
 
h2. Restrictii si precizari
 
. 1 <= N,M <= 100.000
 
. -100.000 <= a[i] <= 100.000
 
. subsecvetele alese trebuie sa contina cel putin un element.
 
h2. Exemplu
 
 
|sequencequery.in |sequencequery.out |Explicatie |
 
|8 3 |7 |[ -1 2 3 -2 4 ] -3 8 -3 |
|-1 2 3 -2 4 -3 8 -3 |9 |-1 2 3 [ -2 4 -3 8 -3 ] |
|1 5 |-3 |-1 2 3 -2 4 [ -3 ] 8 -3 |
|4 8 | | |
|6 6 | | |

==Include(page="template/taskheader" task_id="sequencequery")==
 
Se considera un sir {$A = (a{~1~}, a{~2~}, ... , a{~N~})$} format din $N$ numere intregi, precum si $M$ perechi de numere ({$x, y$}). Pentru fiecare pereche de indici ({$x, y$}) ({$1 ≤ x ≤ y ≤ N$}) trebuie determinata subsecventa de suma maxima a subsirului {$a{~x~}, a{~x+1~}, ..., a{~y~}$}.
 
h2. Date de intrare
 
Fisierul de intrare $sequencequery.in$ va contine pe prima linie doua numere intregi $N$ si $M$. Urmatoarea linie va contine $N$ numere intregi separate prin cate un spatiu. Acestea vor reprezenta numerele {$a{~1~}, a{~2~}, ... , a{~N~}$}. Urmatoarele $M$ linii vor contine fiecare cate o pereche de doua numere separate prin cate un spatiu. Acestea vor indica perechile de indici pentru care trebuie determinate sumele maxime ale subsecventelor.
 
h2. Date de iesire
 
Fisierul de iesire $sequencequery.out$ va contine $M$ linii. Fiecare dintre acestea va contine cate un numar intreg care reprezinta suma elementelor din subsecventa considerata optima dupa criteriile exprimate in enuntul problemei.
 
h2. Restrictii si precizari
 
* $1 ≤ N, M ≤ 100 000$
* $-100 000 ≤ a{~i~} ≤ 100 000$
* Subsecventele alese trebuie sa contina cel putin un element
 
h2. Exemplu
 
table(example). |_. sequencequery.in|_. sequencequery.out|
|8 3
-1 2 3 -2 4 -3 8 -3
1 5
4 8
6 6
|7
9
-3 |
 
h3. Explicatii
 
Subsecventele alese pentru fiecare query in parte sunt ingrosate:
 
* [ -1 **2 3 -2 4** ] -3 8 -3
* -1 2 3 [ -2 **4 -3 8** -3 ]
* -1 2 3 -2 4 [ **-3** ] 8 -3
 
 
==Include(page="template/taskfooter" task_id="sequencequery")==

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

977