#1789. Xor Master
Xor Master
Xor Master
题目描述
标题: Xor Master - Problem - QOJ.ac
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