Sous-tableau de somme maximale
Vous disposez d’un tableau de
n entiers et de q requêtes. Il existe deux types de requêtes : mettre à jour la valeur du tableau à un indice p, et calculer la somme maximale d’un sous-tableau dans la portion [l; r].Le sous-tableau de somme maximale dans
[l; r] est défini comme la portion contiguë dont la somme des éléments est la plus élevée. En d’autres termes, il s’agit de trouver la somme du sous-tableau [l'; r'] ayant la somme la plus grande parmi toutes les sous-portions non vides de [l; r].Entrée
La première ligne de l’entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000).La ligne suivante contient
n entiers séparés par des espaces ( ≤ ≤ ).Les
q lignes suivantes décrivent les requêtes de la forme 1 l r (1 ≤ l ≤ r ≤ n) ou 2 p x (1 ≤ p ≤ n, ≤ x ≤ ), correspondant aux deux types de requêtes :- Obtenir le sous-tableau de somme maximale dans
[l; r].
- Mettre à jour la valeur à la position
pavecx.
Sortie
Pour chaque requête de type 1, le programme doit imprimer la réponse correspondante.
Exemples
Entrée | Sortie |
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