maxq

Time limit: 0.4s
Memory limit: 32MB
Input: maxq.in
Output: maxq.out

Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector VV cu NN numere întregi (numerotate de la 00 la N1N - 1) şi poate efectua următoarele operaţii:

  • schimbarea elementului de pe poziţia pp cu un alt număr întreg;
  • aflarea subsecvenţei de sumă maximă din VV inclusă între indicii aa şi bb;

Cerinţă

Ajutaţi-l pe Johnie să efectueze repede operaţiile de mai sus.

Date de intrare

Fisierul maxq.in conţine pe prima linie numărul NN reprezentând dimensiunea vectorului. Pe următoarea linie se găsesc NN elemente reprezentând valorile iniţiale ale vectorului. Urmatoarea linie conţine MM, reprezentând numărul de operaţii. Pe fiecare dintre următoarele MM linii sunt descrise cele MM 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 ii a vectorului se înlocuieşte cu numarul întreg pp;
  • 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 aa şi b (ab)b \ (a \leq b);

Date de ieşire

Fişierul 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 ii se cere să se afişeze un singur număr reprezentând suma maximă ce se poate obţine în contextul întrebării ii din fişierul de intrare (i=1,2,)(i=1,2,\dots); în cazul în care vor exista doar subsecvenţe de sumă negativă se va afişa 0.

Restricţii si precizări

  • 1N200 0001 \leq N \leq 200 \ 000
  • 1M200 0001 \leq M \leq 200 \ 000
  • toate elementele vectorului aparţin intervalului [100 000,100 000][-100 \ 000, 100 \ 000]
  • 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%20\% din teste se garantează N5 000N \leq 5 \ 000

Exemplu

maxq.in

5
1 -10 4 -1 9
4
1 0 3
0 1 1
1 0 3
1 2 4	

maxq.out

4
6
12

Explicații

Pentru prima întrebare se alege subsecvenţa formată de elementul pe poziţia 22 din vector. Pentru a doua întrebare se aleg primele 33 elemente din vector (elementul de pe poziţia 11 a fost schimbat). Pentru a treia întrebare se aleg toate elementele din intervalul cerut.

Problem info

ID: 157

Editor: liviu

Author:

Source: ONI 2007 XI-XII: Ziua 1 Problema 2

Tags:

ONI 2007 XI-XII

Log in or sign up to be able to send submissions!