Bereichs-XOR-Abfragen
Sie haben ein Array mit
n Elementen sowie q Abfragen. Dabei gibt es zwei Arten von Abfragen:- Ermitteln Sie das XOR (exklusives OR) im angegebenen Bereich.
- Aktualisieren Sie das Array an der vorgegebenen Position.
Ihre Aufgabe besteht darin, diese Abfragen effizient zu verarbeiten.
Input
Die erste Zeile des Inputs enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000). Diese geben die Anzahl der Elemente im Array und die Anzahl der Abfragen an.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (). Diese stellen die Anfangswerte des Arrays dar.Die nächsten
q Zeilen beschreiben jeweils eine Abfrage:- Bei einer Bereichs-XOR-Abfrage beginnt die Zeile mit der Zahl
1. Anschließend folgen zwei ganze Zahlen und (). Diese geben den Indexbereich[]an, für den der XOR-Wert berechnet werden soll.
- Bei einer Aktualisierungs-Abfrage beginnt die Zeile mit der Zahl
2. Danach folgen zwei ganze Zahlen und (). Dies ist die Position im Array, die aktualisiert werden soll, und der neue Wert des Elements.
Output
Geben Sie für jede Bereichs-XOR-Abfrage den berechneten XOR-Wert der entsprechenden Array-Elemente auf einer neuen Zeile aus.
Examples
Eingabe | Ausgabe |
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