Առավելագույն գումար ունեցող ենթազանգված
Ձեզ տրված է
n ամբողջ թվերով զանգված և q հարցում: Հարցումների երկու տեսակ կա. կամ փոփոխում եք զանգվածի արժեքը տրված p ինդեքսում, կամ հայտնաբերում եք [l; r] ենթազանգվածում այն ենթազանգվածը, որը ունի էլեմենտների առավելագույն գումարը:«[l; r]» ենթազանգվածի առավելագույն գումար ունեցող ենթազանգվածը սահմանված է որպես շարունակական այն տակ-зանգվածը, որի էլեմենտների գումարը ամենամեծն է տվյալ միջակայքում: Այլ կերպ ասած, անհրաժեշտ է գտնել «[l'; r']» ենթազանգվածի գումարը, որտեղ այդ գումարը առավելագույնն է
[l; r] տիրույթում գտնվող բոլոր հնարավոր (ոչ դատարկ) ենթազանգվածների մեջ:Մուտք
Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ
n և q (1 ≤ n, q ≤ 100 000):Հաջորդ տողում տրված են
n ամբողջ թվեր, որոնք բաժանված են բացատներով ( ≤ ≤ ):Հաջորդ
q տողերում տրված են հարցումները՝ либо 1 l r (1 ≤ l ≤ r ≤ n) либо 2 p x (1 ≤ p ≤ n, ≤ x ≤ ), որոնք համապատասխանում են հետևյալ երկու գործողություններից որևէ մեկին.- Գտնել
[l; r]ենթազանգվածում առավելագույն գումար ունեցող ենթազանգվածը։
- Թարմացնել (փոփոխել) զանգվածի
p-րդ էլեմենտի արժեքըx-ով։
Ելք
Յուրաքանչյուր (1-ին տեսակի) հարցման համար ծրագիրը պետք է տպի տվյալ հարցման պատասխանը:
Օրինակներ
Մուտք | Ելք |
8 4
-2 1 -3 4 -7 2 1 -5
1 2 6
2 5 0
1 2 6
1 1 2 | 4
6
1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB