XOR-запросы по диапазону (Range XOR Queries)
Вам дан массив из
n элементов и q запросов. Существует два типа запросов:- Получить XOR (исключающее ИЛИ) в заданном диапазоне
- Обновить значение массива в указанной позиции
Ваша задача – эффективно обработать эти запросы.
Входные данные
Первая строка содержит два целых числа
n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и число запросов соответственно.Вторая строка содержит
n целых чисел, разделённых пробелами: (). Это исходные элементы массива.Далее следуют
q строк, каждая из которых описывает один запрос:- Для запросов XOR по диапазону: строка начинается с числа
1, за которым следуют два числа и (), обозначающие диапазон индексов[], по которому нужно вычислить XOR.
- Для запросов на обновление массива: строка начинается с числа
2, за которым следуют два числа и (). Они означают позицию в массиве и новое значение, которое необходимо записать.
Выходные данные
Для каждого запроса XOR по диапазону на отдельной строке выведите результат операции XOR по указанному диапазону.
Примеры
Входные данные | Выходные данные |
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