Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector V cu N numere întregi (numerotate de la 0 la N-1) şi poate efectua următoarele operaţii:
- schimbarea elementului de pe poziţia p cu un alt număr întreg;
- aflarea subsecvenţei de sumă maximă din V inclusă între indicii a şi b;
Cerinţă
Ajutaţi-l pe Johnie să efectueze repede operaţiile de mai sus.
Date de intrare
Fişierul de intrare maxq.in conţine pe prima linie numărul N reprezentând dimensiunea vectorului. Pe următoarea linie se găsesc N elemente reprezentând valorile iniţiale ale vectorului. Urmatoarea linie conţine M, reprezentând numărul de operaţii. Pe fiecare dintre următoarele M linii sunt descrise cele M operaţii în forma următoare:
- “0 i p”: numărul 0 de la început codifică faptul că operaţia curentă este una de schimbare; astfel elementul de pe poziţia i a vectorului se înlocuieşte cu numarul întreg p;
- “1 a b”: numărul 1 de la început codifică faptul că operaţia curentă este o întrebare; astfel se cere să se afle subsecvenţa de sumă maximă din vector inclusă între indicii a şi b (a≤b);
Date de ieşire
Fişierul de ieşire maxq.out trebuie să conţină un număr de linii egal cu numărul de întrebări din fişierul de intrare. Pe linia i se cere să se afişeze un singur număr reprezentând suma maximă ce se poate obţine în contextul întrebării i din fişierul de intrare (i=1,2,...); în cazul în care vor exista doar subsecvenţe de sumă negativă se va afişa 0.
Restricţii
1 ≤ N ≤ 200000;
1 ≤ M ≤ 200000;
toate elementele vectorului aparţin intervalului [-100000, 100000];
definim o subsecvenţă ca fiind un şir de termeni consecutivi din vector, iar suma ei se obţine adunând elementele ce o compun;
există cel puţin o întrebare.
pentru 20% din teste se garantează N ≤ 5000
Exemple
maxq.in
maxq.out
Explicaţii
5
1 10 4 1 9
4
1 0 3
0 1 1
1 0 3
1 2 4
4
6
12
Pentru prima întrebare se alege subsecvenţa formată de elementul pe poziţia 2 din vector. Pentru a 2-a întrebare se aleg primele 3 elemente din vector (elementul de pe poziţia 1 a fost schimbat). Pentru a 3-a întrebare se aleg toate elementele din intervalul cerut.