bzoj#P3984. 最大异或和

最大异或和

题目描述

我有一个数列a[1],a[2],…,a[n],每个a[i]是小于2^m的非负整数。 现在请您实现三种操作,格式说明如下: 1 x y w 对于所有x<=i<=y,将a[i]修改为a[i] xor w; 2 x y w 对于所有x<=i<=y,将a[i]修改为w; 3 从a[1],a[2],…,a[n]中选出若干个数,使它们的xor和最大,并输出这个最大值。 (xor表示按位异或运算)

输入格式

第一行三个整数n,m,q。 接下来n行为初始时a[1],a[2],…,a[n]的值。 接下来q行,每行表示一个操作。 (a[i],w的数值均用恰好m位的二进制01串表示,左边是最高位,右边是最低位,不足m位的在左边补0)

输出格式

对于每个3号操作,输出一个m位01串作为回答。

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

提示

N<=2000,M<=2000,Q<=2000 所有数据中,1,2操作保证1<=x<=y<=n

题目来源

2015年集训队互测