Consultas de Máximo em Intervalos
Tem à sua disposição um array de
n elementos e q consultas. Existem dois tipos de consultas:- Obter o valor máximo no intervalo especificado
- Atualizar o array na posição indicada
A sua tarefa é processar estas consultas de forma eficiente.
Entrada
A primeira linha da entrada contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam a quantidade de elementos no array e o número de consultas, respetivamente.A segunda linha contém
n inteiros separados por espaços, (), que descrevem os elementos iniciais do array.As
q linhas seguintes descrevem cada consulta:- Para consultas de máximo em intervalos (range maximum queries): a linha começa com o número
1, seguido de dois inteiros e (), que indicam o intervalo de índices[]no qual se pretende determinar o valor máximo.
- Para consultas de atualização do array (array update queries): a linha começa com o número
2, seguido de dois inteiros e (), que correspondem à posição do elemento a atualizar e ao seu novo valor.
Saída
Para cada consulta de máximo em intervalo, imprima o valor máximo correspondente ao intervalo numa linha separada.
Exemplos
Entrada | Saída |
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