Consulta Min-Max em Intervalos
Recebes um array de
n elementos e q consultas. Existem dois tipos de consulta:- Obter o mínimo e o máximo num intervalo específico.
- Atualizar o array numa dada posição.
O teu objetivo é processar as consultas de forma eficiente.
Input
A primeira linha do input contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam o número de elementos do array e o número de consultas, respetivamente.A segunda linha contém
n inteiros separados por espaço, (), que são os valores iniciais do array.As
q linhas seguintes descrevem as consultas:- Para as consultas de obter o par mínimo e máximo num intervalo: a linha começa com o número
1, seguido de dois inteiros e (), indicando o intervalo de índices[]para o qual é necessário calcular o mínimo e o máximo.
- Para as consultas de atualização do array: a linha começa com o número
2, seguido de dois inteiros e (), que indicam o índice do elemento a atualizar e o seu novo valor.
Output
Para cada consulta de obter o par mínimo e máximo no intervalo, imprime o mínimo e o máximo dos elementos nesse intervalo em linhas separadas.
Exemplos
Entrada | Saída |
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