配点 : 500 点
問題文
长度 N 整数序列 有 A_1, A_2, \ldots, A_N 。下面 按顺序处理 Q 查询。
- 值为 L_i 以上 R_i 选择下面的所有元素并回答它们的异或。然后是所有选中的元素 更新至 X_i 。 然而,L_i 以上 R_i 以下整数是 1 如果不存在,答案是 0 。
什么是异或?
整数 c_1, c_2, ..., c_n 的异或 X 定义如下。 当
- X 表示为二进制数时, 2^k (k \ge 0) 的位值为c_1, c_2, ..., c_n 当表示为二进制数时 2^k 的位值为 如果有奇数个 1 如果有奇数个 1,如果数字是偶数 0 。
例如,3 和
我讨厌 5 的异或是 6 (二进制表示法: 011 和
我讨厌 101 的异或是 110 )。
打印第
制約
- 1\le N\le 3\times 10^5
- 1\le Q\le 2\times 10^5
- 0\le A_i\le 10^9
- 0\le L_i\le R_i\le 10^9
- 0\le X_i\le 10^9
- 输入全为整数。
入力
输入如下格式从标准输入给出。
N\ Q A_1\ A_2\ \ldots\ A_N L_1\ R_1\ X_1 L_2\ R_2\ X_2 \vdots L_Q\ R_Q\ X_Q
出力
Q 行。 i (1\le i\le Q) 在线 i 个查询的答案。
入力例 1
5 2 7 4 1 5 9 7 10 2 2 8 5
出力例 1
14 1
- 1 在第二个查询中,7 以上 10 以下整数是 7 和 我讨厌 9 的 2 所以这些的异或 输出 14 。 那么这个 2 一 更新为 2 并且编号规则为 输出 \{2,4,1,5,2\} 。
- 2 在第二个查询中,2 以上 8 以下整数是 2, 4, 5, 2 的 4 所以这些的异或 输出1 。 那么这个 4 一 更新为 5 并且编号规则为 输出 \{5,5,1,5,5\} 。
入力例 2
1 1 5 1 3 2
出力例 2
0
满足条件 如果 A_i 不存在,则答案为 0 。目前不会进行任何更新。
入力例 3
15 10 76 87 42 60 30 58 52 82 42 13 81 8 97 5 87 4 11 92 56 60 68 90 100 24 30 35 15 12 17 53 24 32 31 0 6 85 74 82 55 69 72 30 50 61 49
出力例 3
13 6 97 30 2 24 0 79 0 3