Range Min-Max Query
Ti viene fornito un array di
n elementi e q interrogazioni (query). Esistono due tipi di query:- Ottenere il valore minimo e massimo all'interno di un determinato intervallo.
- Aggiornare l’array in una posizione specifica.
Il tuo obiettivo è gestire queste query in modo efficiente.
Input
La prima riga dell’input contiene due interi
n e q (1 ≤ n, q ≤ 100 000), che indicano rispettivamente il numero di elementi nell’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 una query:- Per le query che richiedono il minimo e il massimo nell’intervallo: la riga inizia con il numero
1, seguito da due interi e (), che specificano l’intervallo di indici[]su cui calcolare minimo e massimo.
- Per le query di aggiornamento dell’array: la riga inizia con il numero
2, seguito da due interi e (), che indicano l’indice dell’elemento da aggiornare e il suo nuovo valore.
Output
Per ogni query che richiede il minimo e il massimo in un intervallo, stampa il valore minimo e il valore massimo nell’intervallo specificato, ciascuno su una riga separata.
Examples
Input | Output |
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