#1976. 最大异或和

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

最大异或和

最大异或和

题目描述

标题: 最大异或和 - Problem - QOJ.ac

#4256. 最大异或和

Statistics

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