Interrogations sur la valeur maximale dans un intervalle (Range Maximum Queries)
On vous donne un tableau de
n éléments et q requêtes. Il existe deux types de requêtes :- Obtenir la valeur maximale dans un intervalle donné
- Mettre à jour le tableau à un emplacement précis
Votre tâche consiste à traiter ces requêtes de manière efficace.
Entrée
La première ligne de l'entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), représentant respectivement le nombre d'éléments dans le tableau et le nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces (1 ≤ a_i ≤ 10^9), qui sont les éléments initiaux du tableau.Les
q lignes suivantes décrivent chacune une requête :- Pour les requêtes de maximum sur un intervalle : la ligne commence par le chiffre
1, suivi de deux entiers et (1 ≤ li ≤ ri ≤ n), indiquant l’intervalle d’indices[ $$l_i, r_i$$ ]dont il faut déterminer la valeur maximale.
- Pour les requêtes de mise à jour du tableau : la ligne commence par le chiffre
2, suivi de deux entiers et (1 ≤ pi ≤ n, 1 ≤ xi ≤ 10^9), qui indiquent la position de l’élément à mettre à jour et sa nouvelle valeur.
Sortie
Pour chaque requête de maximum sur un intervalle, affichez la valeur maximale dans l’intervalle correspondant sur une ligne distincte.
Exemples
Entrée | Sortie |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 4
9
7 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB