markdown

E. 区间异或与求和

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入（stdin）
输出：标准输出（stdout）

题目描述

你有一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成的数组 $a$。你可以对该数组执行以下两种操作：

• 计算数组在区间 $[l, r]$ 上的元素之和，即求值 $a_l + a_{l+1} + \dots + a_r$。
• 将区间 $[l, r]$ 上的每个数组元素与给定的数 $x$ 进行异或运算，即执行 $a_i = a_i \oplus x$。该操作会改变恰好 $r - l + 1$ 个数组元素。

表达式 $x \oplus y$ 表示对数字 $x$ 和 $y$ 进行按位异或运算。该操作在所有现代编程语言中均存在，例如在 C++ 和 Java 中标记为 ^，在 Pascal 中标记为 xor。

你有一个包含 $m$ 个上述类型操作的列表。你的任务是执行所有给定的操作，并在每次求和查询时输出得到的结果。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 数组的大小。
第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^6$）—— 原始数组。
第三行包含一个整数 $m$（$1 \le m \le 5 \times 10^4$）—— 对数组执行的操作数量。
接下来的 $m$ 行中，第 $i$ 行首先包含一个整数 $t_i$（$1 \le t_i \le 2$）—— 第 $i$ 个查询的类型。

• 如果 $t_i = 1$，则为求和查询，后面跟着两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。
• 如果 $t_i = 2$，则为修改数组元素的查询，后面跟着三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n$，$1 \le x_i \le 10^6$）。

每行中的数字之间由单个空格分隔。

输出格式

对于每个类型为 $1$ 的查询，在一行中输出给定区间上数字的和。按照查询在输入中出现的顺序输出答案。

注意：在 C++ 中，请勿使用 %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