QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+2]

# 7765. Xor Master

Statistics

「集训队互测」是由 CCF 自主研发的一款开放算法竞赛游戏,在这里,最强的参赛选手将成为「集集国王」,导引 OI 之力,击败强大的题目,找回失散的 IOI 金牌。

要想成为「集集国王」,你就要先打败「异或尊主」(The Xor Master)。

「异或尊主」向你发起了挑战:

题目描述

下文中将异或符号记作

「异或尊主」有一个长为 n 的序列 a,和一个初始为空的集合 S0

定义 xor(S) 表示集合 S 中所有元素的异或和,若 S 为空则是 0

定义 g(x,S)=maxTS(xxor(T))

定义 f(l,r)=g(\oplus_{i=l}^{r} a_i, S_0) \oplus_{i=l}^{r}a_i 表示 a_l\sim a_r 的异或和。

「异或尊主」会进行 Q 次操作或询问:

  • 1 x v:将 a_x 异或上 v
  • 2 x:将 x 加入集合 S_0 中。
  • 3 l r:询问 \sum\limits_{i=l}^r f(l,i) 的值。由于答案可能很大,只需要输出答案 \bmod 2^{64} 的值。

你急于成为「集集国王」,请快速回答出「异或尊主」的询问来将他打败吧!

输入格式

第一行两个整数 n,Q

第二行 n 个非负整数 a_1\sim a_n

接下来 Q 行,每行描述一次操作或询问,格式见题目描述。

输出格式

对于每次询问输出一行一个整数,表示答案 \bmod 2^{64} 的值。

样例

input 1

5 5
5 7 1 4 3
3 1 3
1 2 4
3 1 5
2 3
3 1 5

output 1

10
21
25

input 2

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

output 2

32
18
25

数据范围

子任务编号 分值 n \leq Q \leq m = 特殊性质
1 10 2000 2\,000 32
2 10 5 \times 10^5 10^5 64 A,B
3 10 B
4 10 10^5 32 A,C
5 15 5 \times 10^5 64
6 15 10^5 32
7 30 5 \times 10^5 64

特殊性质 \mathrm{A} :不存在 1 类操作。

特殊性质 \mathrm{B} :不存在 2 类操作。

特殊性质 \mathrm{C} :对于所有询问,保证 l=1