T1 - Teploty 1

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Ústav geografie na Prírodovedeckej fakulte UPJŠ v Košiciach sa zaoberá aj teplotnými zmenami za posledné desaťročia. Podarilo sa im dať dokopy historické aj aktuálne údaje a chceli by vedieť zisťovať najvyššiu, najnižšiu aj priemernú teplotu v jednotlivých časových úsekoch, na to potrebujú systém ktorý vie vypočítať minimum, maximum aj súčet súvislej podpostupnosti.

Vytvorili si vlastný program na výpočet, ale zistili, že je veľmi pomalý. Navyše pri kontrole hodnôt za staršie obdobia našli nezrovnalosti so staršími publikáciami. Ako vysvitlo niektoré zaznamenané hodnoty nie sú správne (mohla nastať chyba v spracovaní papierových údajov OCR programom, dokonca v jednom roku niektoré chýbajúce údaje boli nahradené hodnotou -1, ale taká sa v lete v Košiciach nevyskytuje).

Pomôžte im vytvoriť program, ktorú bude vedieť nielen počítať požadované hodnoty súvislej podpostupnosti, ale bude vedieť aj meniť ich hodnotu ...

Úloha

Pre zadané hodnoty postupnosti teplôt vypočítajte požadované hodnoty na súvislých podpostupnostiach a prípadne upravujte chybné hodnoty.

Vstup

V prvom riadku súboru sa nachádzajú dve celé čísla, počet hodnôt N a počet úloh U ≤ 20 000.

Nasleduje 1 riadok obsahujúci počiatočné hodnoty postupnosti.

Každý z nasledujúcich U riadkov obsahuje zadanie jednej úlohy v jednom z možných tvarov:

+ x y ... súčet podpostupnosti od indexu x po index y (vrátane), číslovanie od jedna.
< x y ... najmenšiu hodnotu v podpostupnosti od indexu x po index y (vrátane).
> x y ... najväčšiu hodnotu v podpostupnosti od indexu x po index y (vrátane).
z x y ... zmena hodnoty podpostupnosti na indexe x na hodnotu y (vrátane).

Výstup

Výstupom programu je pre každú výpočtovú úlohu jeden riadok obsahujúci jedno kladné celé číslo - hľadanú hodnotu.

T1

3 ≤ N ≤ 2 000

T2

3 ≤ N ≤ 100 000
Obsahuje iba úlohy na súčet +.

T3

3 ≤ N ≤ 100 000

Príklad

Vstup:

7 6
2 4 1 5 1 1 2
+ 1 7
< 1 2
> 2 5
z 4 3
> 2 5
+ 1 7

Výstup:

Pozn.: Po zmene štvrtej hodnoty sa zmení celkový súčet aj najväčšia hodnota v podpostupnosti medzi indexami 2 a 5.

22 Domáce 2