← 返回题目列表

Codeforces · 242/E

E. 段上的异或

中文机器翻译题面 查看原题

你有一个数组 a,由 n 个整数 a1, a2, ..., an 组成。您可以对此数组执行两种操作:

1、计算[l, r]段上当前数组元素的和,即计数值al + al + 1 + ... + ar。
2. 对段 [l, r] 上的每个数组元素进行与给定数字 x 的异或运算,即执行 $$a_{l} = a_{l} \oplus x, a_{l+1} = a_{l+1} \oplus x, \ldots, a_{r} = a_{r} \oplus x$$。该操作恰好改变了 r - l + 1 个数组元素。

表达式 $$x \oplus y$$ 表示对数字 x 和 y 进行按位异或运算。给定的操作存在于所有现代编程语言中,例如在 C++ 和 Java 语言中它被标记为“^”,在 Pascal 中被标记为“xor”。

您已获得指定类型的 m 个操作的列表。您的任务是执行所有给定的操作,对于每个求和查询,您应该打印得到的结果。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 数组的大小。第二行包含空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 106) — 原始数组。

第三行包含整数 m (1 ≤ m ≤ 5·104) — 数组的操作次数。接下来的 m 行中的第 i 行首先包含一个整数 ti (1 ≤ ti ≤ 2) — 第 i 个查询的类型。如果ti = 1,则这是求和的查询,如果ti = 2,则这是更改数组元素的查询。如果第 i 个操作是类型 1,则接下来是两个整数 li, ri (1 ≤ li ≤ ri ≤ n)。如果第 i 个操作是类型 2,则接下来是三个整数 li、ri、xi (1 ≤ li ≤ ri ≤ n,1 ≤ xi ≤ 106)。行上的数字由单个空格分隔。

输出

对于类型 1 的每个查询,在单行中打印给定段上的数字总和。按照查询在输入中的顺序打印查询的答案。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

输出 #1

26
22
0
34
11

输入 #2

6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3

输出 #2

38
28