#1976. 最大异或和
最大异或和
最大异或和
题目描述
标题: 最大异或和 - Problem - QOJ.ac
#4256. 最大异或和
The problem was used in the following contests:
我有一个数列 a1,a2,…,an,每个 ai 都是小于 2m 的非负整数。
现在请您实现三种操作,格式说明如下:
- 1 x y w:对于所有 x≤i≤y,将 ai 修改为 aixorw。其中 w 是一个小于 2m 的非负整数。
- 2 x y w:对于所有 x≤i≤y,将 ai 修改为 w。其中 w 是一个小于 2m 的非负整数。
- 3:从 a1,a2,…,an 中选出若干个数,使得选出的数异或和最大。请输出这个最大值。
这里 xor 表示按位异或运算,x1,x2,…,xl 的异或和是指 x1xorx2xor…xorxl。
输入格式
第一行三个正整数 n,m,q。
接下来 n 行为初始时 a1,a2,…,an 的值。
接下来 q 行,每行表示一个操作。操作的格式如前所述。保证 1≤x≤y≤n。
a1,…,an 和 w 均用恰好 m 位的 01 串表示这个数的二进制表示。左边是最高位,右边是最低位,不足 m 位的在左边补 0。
输出格式
对于每个 3 号操作,输出一个 m 位 01 串表示答案的二进制表示。
样例一
input
3 4 7
0000
0011
0110
3
1 2 3 0010
3
2 1 2 0010
3
2 1 3 0000
3
output
0110
0101
0110
0000
限制与约定
测试点编号 n m q 特殊限制 1=10=10=1000无2=500=500=103=120=120=1204=2000=2000=105=1800=1800=18001,2 操作中 x=y6只有 1,3 操作7只有 2,3 操作8=1500=1500=1500无9=1800=1800=180010=2000=2000=2000
**时间限制:**2s
**空间限制:**256MB
来源
中国国家集训队互测2015 - By 金策
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4 7
0000
0011
0110
3
1 2 3 0010
3
2 1 2 0010
3
2 1 3 0000
3
0110
0101
0110
0000