Fişierul intrare/ieşire:	maxq.in, maxq.out	Sursă	ONI 2007, clasele 11-12
Autor	Daniel Pasaila	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.5 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Maxq

Johnie a inceput sa se joace cu un vector de numere. El dispune initial de un vector V cu N numere intregi (numerotate de la 0 la N-1) si poate efectua urmatoarele operatii:

• schimbarea elementului de pe pozitia p cu un alt numar intreg;
• aflarea subsecventei de suma maxima din V inclusa intre indicii a si b;

Cerinta

Ajutati-l pe Johnie sa efectueze repede operatiile de mai sus.

Date de intrare

Fisierul maxq.in contine pe prima linie numarul N reprezentand dimensiunea vectorului. Pe urmatoarea linie se gasesc N elemente reprezentand valorile initiale ale vectorului. Urmatoarea linie contine M, reprezentand numarul de operatii. Pe fiecare dintre urmatoarele M linii sunt descrise cele M operatii in forma urmatoare:

• 0 i p: numarul 0 de la inceput codifica faptul ca operatia curenta este una de schimbare; astfel elementul de pe pozitia i a vectorului se inlocuieste cu numarul intreg p;
• 1 a b: numarul 1 de la inceput codifica faptul ca operatia curenta este o intrebare; astfel se cere sa se afle subsecventa de suma maxima din vector inclusa intre indicii a si b (a ≤ b);

Date de iesire

Fisierul maxq.out trebuie sa contina un numar de linii egal cu numarul de intrebari din fisierul de intrare. Pe linia i se cere sa se afiseze un singur numar reprezentand suma maxima ce se poate obtine in contextul intrebarii i din fisierul de intrare (i=1,2,...); in cazul in care vor exista doar subsecvente de suma negativa se va afisa 0.

Restrictii

• 1 ≤ N ≤ 200 000;
• 1 ≤ M ≤ 200 000;
• toate elementele vectorului apartin intervalului [-100000, 100000];
• definim o subsecventa ca fiind un sir de termeni consecutivi din vector, iar suma ei se obtine adunand elementele ce o compun;
• exista cel putin o intrebare.
• pentru 20% din teste se garanteaza N ≤ 5000

Exemplu

Explicatie

Pentru prima intrebare se alege subsecventa formata de elementul pe pozitia 2 din vector. Pentru a 2-a intrebare se aleg primele 3 elemente din vector (elementul de pe pozitia 1 a fost schimbat). Pentru a 3-a intrebare se aleg toate elementele din intervalul cerut.

Cum se trimit solutii?