0416. Поксорим?

Имя входного файла:	queries.in
Имя выходного файла:	queries.out
Ограничение по времени:	3 s
Ограничение по памяти:	256 megabytes

Богдан работает программистом в одной секретной фирме. В его обязанности входит обслуживание вычислительного устройства "TopSecret666". Это очень странное устройство. Оно имеет N ячеек памяти для хранения данных и M ячеек памяти для хранения команд на изменение данных. Ячейки данных имеют номера 1 …N. Ячейки команд имеют номера 1 …M. Данные – это набор из N целых чисел. Команды – это M троек целых чисел l_i, r_i, x_i. Каждая команда заключается в следующем: для каждой ячейки данных j, где j находится в промежутке между l_i и r_i включительно, взять хранящееся в ней значение A_j и поместить в нее значение A_J \oplus x_i. \oplus – исключающее или. Сначала в устройство заносятся данные, затем заполняются команды. Потом, на терминал устройства поступают запросы двух видов.

1. задаётся отрезок в памяти команд с границами L и R включительно. Команды из этого отрезка отправляются на выполнение.
2. задаётся отрезок в памяти данных с границами L и R включительно. Числа из этого отрезка суммируются и результат выводится на экран устройства.

По какой-то причине, программа обработки запросов перестала работать. Богдана попросили переписать её. Но у Богдана нет нужного количества свободного времени, а работу нужно выполнить в кратчайший срок. Поэтому он обратился к вам за помощью.

Формат входного файла

Первая строка содержит одно число N – количество ячеек памяти для хранения данных. 1 ≤ N ≤ 10⁵. В следующей строке находятся N чисел A_i – начальные данные. 0 ≤ A_i ≤ 10⁹. Следующая строка содержит число M – количество ячеек памяти для хранения команд. 1 ≤ M ≤ 10³. Следующие M строк содержат по числа l_i, r_i, x_i – описания команд. 1 ≤ l_i, r_i, ≤ M.0 ≤ x_i ≤ 10⁹. Далее следует число T – число запросов. Следующие T строк содержат по числа t_i, L_i, R_i – описание запросов. 1 ≤ t ≤ 2 – тип запроса. L, R – границы отрезка памяти. Гарантируется, что запросы не выходят за пределы соответствующей области памяти.

Так сложилось, что запросов второго типа поступило не более 50.

Формат выходного файла

Для каждого запроса второго типа выведите в новой строке результат выполнения запроса.

Пример:

queries.in	queries.out
5 1 3 3 5 5 2 1 2 1 4 5 1 10 2 1 5 2 3 3 1 1 2 2 1 2 1 1 1 2 4 5 2 1 5 1 1 1 1 1 2 2 1 5	17 3 2 8 15 17

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати