maxq

Maxq

== include(page="template/taskheader" task_id="maxq") ==

Poveste si cerinta...

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$};
 
h2. Cerinta
 
Ajutati‑l pe Johnie sa efectueze repede operatiile de mai sus.

h2. 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$});
 

h2. 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$}.

h2. 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$}
 

h2. Exemplu
table(example). |_. maxq.in |_. maxq.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
1 -10 4 -1 9
4
1 0 3
0 1 1
1 0 3
1 2 4
| 4
6
12

|
h3. 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.

== include(page="template/taskfooter" task_id="maxq") ==