【集训队互测2015】最大异或和

正文索引 [隐藏]

描述

我有一个数列 a1,a2,,an,每个 ai 都是小于 2m 的非负整数。
现在请您实现三种操作,格式说明如下:

  • 1 x y w:对于所有 xiy,将 ai 修改为 aixorw。其中 w 是一个小于 2m 的非负整数。
  • 2 x y w:对于所有 xiy,将 ai 修改为 w。其中 w 是一个小于 2m 的非负整数。
  • 3:从 a1,a2,,an 中选出若干个数,使得选出的数异或和最大。请输出这个最大值。

这里 xor 表示按位异或运算,x1,x2,,xl 的异或和是指 x1xorx2xorxorxl

输入格式

第一行三个正整数 n,m,q
接下来 n 行为初始时 a1,a2,,an 的值。
接下来 q 行,每行表示一个操作。操作的格式如前所述。保证 1xyn
a1,,anw 均用恰好 m 位的 01 串表示这个数的二进制表示。左边是最高位,右边是最低位,不足 m 位的在左边补 0

输出格式

对于每个 3 号操作,输出一个 m 位 01 串表示答案的二进制表示。

样例一

input

output

限制与约定

测试点编号 n m q 特殊限制
1 =10 =10 =1000
2 =500 =500 =10
3 =120 =120 =120
4 =2000 =2000 =10
5 =1800 =1800 =1800 1,2 操作中 x=y
6 只有 1,3 操作
7 只有 2,3 操作
8 =1500 =1500 =1500
9 =1800 =1800 =1800
10 =2000 =2000 =2000

时间限制:2s
空间限制:256MB

来源

中国国家集训队互测2015 – By 金策

下载

样例数据下载

题解

我只会写40分、、、高斯消元变成一个三角矩阵、然后顺着高位贪心、、


[remind]真正的题解:sol.pdf[/remind]