Requêtes XOR sur un Intervalle
Vous disposez d’un tableau composé de
n éléments ainsi que de q requêtes. Il existe deux types de requêtes :- Calculer le XOR (opération exclusive OU) sur un intervalle spécifié.
- Mettre à jour la valeur d’un élément du tableau à un indice donné.
Votre objectif est de traiter ces requêtes de manière efficace.
Entrée
La première ligne de l’entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), qui indiquent respectivement le nombre d’éléments du tableau et le nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces, (), représentant les éléments initiaux du tableau.Les
q lignes qui suivent décrivent chacune une requête :- Pour les requêtes de type XOR sur un intervalle : la ligne commence par le chiffre
1, suivi de deux entiers et (), indiquant l’intervalle[]pour lequel il faut calculer la valeur XOR.
- Pour les requêtes de mise à jour du tableau : la ligne commence par le chiffre
2, suivi de deux entiers et (), où correspond à la position de l’élément à modifier et désigne sa nouvelle valeur.
Sortie
Pour chaque requête de type XOR sur un intervalle, affichez sur une ligne distincte la valeur du XOR des éléments compris dans l’intervalle spécifié.
Exemples
Input | Output |
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