Requêtes Min-Max sur un intervalle
Vous disposez d’un tableau de
n éléments ainsi que de q requêtes. Il existe deux types de requêtes :- Obtenir le minimum et le maximum sur un intervalle donné.
- Mettre à jour le tableau à un indice spécifique.
Votre objectif est de 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), qui correspondent respectivement au nombre d’éléments dans le tableau et au nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces (), représentant les éléments initiaux du tableau.Les
q lignes suivantes décrivent chacune une requête :- Pour les requêtes de minimum et maximum sur un intervalle : la ligne commence par
1, suivie de deux entiers et (). Ils définissent l’intervalle[$$l_i, r_i$$]pour lequel on doit déterminer le couple (minimum, maximum).
- Pour les requêtes de mise à jour : la ligne commence par
2, suivie de deux entiers et (). Ils indiquent l’indice de l’élément à mettre à jour ainsi que sa nouvelle valeur.
Sortie
Pour chaque requête de type (minimum, maximum) sur un intervalle, affichez sur des lignes distinctes la valeur minimale et la valeur maximale au sein de l’intervalle spécifié.
Exemples
Entrée | Sortie |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB