← 返回题目列表

AtCoder · cpsco2019_s1_e

E. 异或查询

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

配点 : 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