#1789. Xor Master

    ID: 1789 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1417来源:qoj.ac数据:公开样例线段树

Xor Master

Xor Master

题目描述

标题: Xor Master - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

题目描述

下文中将异或符号记作 ⊕。

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

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

定义 g(x,S)=maxT⊆S(x⊕xor⁡(T))。

定义 f(l,r)=g(⊕i=lrai,S0),⊕i=lrai 表示 al∼ar 的异或和。

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

  • 1 x v:将 ax 异或上 v 。
  • 2 x:将 x 加入集合 S0 中。
  • 3 l r:询问 ∑i=lrf(l,i) 的值。由于答案可能很大,只需要输出答案 mod264 的值。

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

输入格式

第一行两个整数 n,Q。

第二行 n 个非负整数 a1∼an。

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

输出格式

对于每次询问输出一行一个整数,表示答案 mod264 的值。

样例

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≤ Q≤ m= 特殊性质 1 10 2000 2000 32 无 2 10 5×105 105 64 A,B 3 10 B 4 10 105 32 A,C 5 15 5×105 64 6 15 105 32 无 7 30 5×105 64

特殊性质 A:不存在 1 类操作。

特殊性质 B:不存在 2 类操作。

特殊性质 C:对于所有询问,保证 l=1。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 5
5 7 1 4 3
3 1 3
1 2 4
3 1 5
2 3
3 1 5
10
21
25

样例 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
32
18
25