Range Maximum Queries
Ti viene fornito un array di
n elementi e q query. Sono presenti due tipi di query:- Ottenere il valore massimo in un determinato intervallo
- Aggiornare l’array in una posizione specifica
Il tuo obiettivo è gestire queste query in modo efficiente.
Ingresso
La prima riga dell’ingresso contiene due interi
n e q (1 ≤ n, q ≤ 100 000), che indicano rispettivamente il numero di elementi dell’array e il numero di query.La seconda riga contiene
n interi separati da spazio (), che rappresentano gli elementi iniziali dell’array.Le successive
q righe descrivono ciascuna query:- Per le query di tipo range maximum: la riga inizia con il numero
1seguito da due interi e (), che indicano gli indici dell’intervallo[]in cui bisogna calcolare il valore massimo.
- Per le query di aggiornamento dell’array: la riga inizia con il numero
2seguito da due interi e (), che rappresentano la posizione dell’elemento da aggiornare e il suo nuovo valore.
Uscita
Per ogni query di tipo range maximum, stampa su una nuova riga il valore massimo all’interno dell’intervallo specificato.
Esempi
Input | Output |
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