UOJ Logo Universal Online Judge

UOJ

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

统计
$\newcommand\xor{\mathbin{\mathrm{xor}}}$

我有一个数列 $a_1, a_2, \dots, a_n$,每个 $a_i$ 都是小于 $2^m$ 的非负整数。

现在请您实现三种操作,格式说明如下:

  • $1$ $x$ $y$ $w$:对于所有 $x \leq i \leq y$,将 $a_i$ 修改为 $a_i \xor w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
  • $2$ $x$ $y$ $w$:对于所有 $x \leq i \leq y$,将 $a_i$ 修改为 $w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
  • $3$:从 $a_1, a_2, \dots, a_n$ 中选出若干个数,使得选出的数异或和最大。请输出这个最大值。

这里 $\xor$ 表示按位异或运算,$x_1, x_2, \dots, x_l$ 的异或和是指 $x_1 \xor x_2 \xor \dots \xor x_l$。

输入格式

第一行三个正整数 $n,m,q$。

接下来 $n$ 行为初始时 $a_1, a_2, \dots, a_n$ 的值。

接下来 $q$ 行,每行表示一个操作。操作的格式如前所述。保证 $1 \leq x \leq y \leq n$。

$a_1, \dots, a_n$ 和 $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$$= 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$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

来源

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

下载

样例数据下载