Consultas de máximo en un rango (Range Maximum Queries)
Se te proporciona un arreglo de
n elementos y q consultas. Hay dos tipos de consultas:- Obtener el valor máximo en un rango determinado
- Actualizar el arreglo en una posición específica
Tu tarea consiste en procesar estas consultas de forma eficiente.
Input
La primera línea de la entrada contiene dos números enteros
n y q (1 ≤ n, q ≤ 100 000), que representan la cantidad de elementos del arreglo y el número de consultas, respectivamente.La segunda línea contiene
n enteros separados por espacios (), que indican los valores iniciales del arreglo.Las siguientes
q líneas describen cada consulta:- Para las consultas de máximo en un rango: la línea comienza con el número
1seguido de dos enteros y (), que representan el rango de índices[]en el cual se debe calcular el valor máximo.
- Para las consultas de actualización de arreglo: la línea comienza con el número
2seguido de dos enteros y (), que indican la posición del elemento a actualizar y el nuevo valor que se asignará.
Output
Para cada consulta de máximo en un rango, debes imprimir el valor máximo dentro de dicho rango en una línea independiente.
Ejemplos
Entrada | Salida |
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