Interrogazioni XOR su intervalli
Ti viene fornito un array di
n elementi e q interrogazioni. Esistono due tipologie di interrogazioni:- Calcolare l’XOR (OR esclusivo) sugli elementi di un determinato intervallo
- Aggiornare l’array in una posizione specifica
Il tuo compito è elaborare queste interrogazioni 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 interrogazioni.La seconda riga contiene
n interi separati da spazio (), che sono gli elementi iniziali dell’array.Le successive
q righe descrivono ognuna un’interrogazione:- Per le interrogazioni di tipo “range XOR”: la riga inizia con il numero
1seguito da due interi e (), che definiscono la porzione di indici[$$l_i, r_i$$]per cui è necessario calcolare il valore XOR.
- Per le interrogazioni di aggiornamento dell’array: la riga inizia con il numero
2seguito da due interi e (), che specificano la posizione dell’elemento da aggiornare e il nuovo valore.
Output
Per ogni interrogazione di tipo “range XOR”, stampa su una nuova riga il risultato dell’operazione XOR sugli elementi dell’intervallo richiesto.
Esempi
Ingresso | Uscita |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 7
9
3 |
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 1 MB