有一个数列 $a_1, a_2, \dots, a_n$，每个 $a_i$ 都是小于 $2^m$ 的非负整数。
现在需要实现三种操作，格式说明如下：
1 x y w：对于所有 $x \leq i \leq y$，将 $a_i$ 修改为 $a_i \oplus w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
2 x y w：对于所有 $x \leq i \leq y$，将 $a_i$ 修改为 $w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
3：从 $a_1, a_2, \cdots, a_n$ 中选出若干个数，使得选出的数异或和最大。请输出这个最大值。
这里 $\oplus$ 表示按位异或运算，$x_1, x_2, \cdots, x_l$ 的异或和是指 $x_1 \oplus x_2 \oplus \dots \oplus x_l$。
第一行包含三个正整数 $n, m, q$ ($n, m, q \leq 2000$)。
接下来 $n$ 行，每行一个二进制表示的整数，为初始时 $a_1, a_2, \dots, a_n$ 的值 ($0 \leq a_i \leq 2^m - 1$) 。
接下来 $q$ 行，每行表示一个操作。操作的格式如前所述。保证 $1 \leq x \leq y \leq n$。
$a_1, \cdots, a_n$ 和 $w$ 均用恰好 $m$ 位的 $\texttt 0/\texttt 1$ 串表示这个数的二进制表示。左边是最高位，右边是最低位，不足 $m$ 位的在左边补 $0$。
对于每个操作 3，输出一行一个长度为 $m$ 的 $\texttt 0/\texttt 1$ 串，表示答案的二进制表示。
注意到操作 3 ——求一些数的 "最大异或和"，不难想到应该使用线性基 (动态 Gauss 消元) 来处理。
但是这些数有区间修改和区间赋值一些奇怪的操作，又该怎么处理呢？
先考虑操作 1 (区间异或上一个数)。我们有一个平凡但重要的结论：
向量 $\mathbf v_1, \mathbf v_2, \cdots, \mathbf v_k$ 张成的线性空间与 $\mathbf v_1, \mathbf v_2 - \mathbf v_1, \mathbf v_3 - \mathbf v_2, \cdots, \mathbf v_k - \mathbf v_{k-1}$ 张成的线性空间相同。
既然两组向量所能张成的线性空间相同，因此能异或 (线性组合) 出的最大数当然相同啦。
因此我们对原序列 (异或) 差分，就将区间修改 (异或) 转化为了单点修改。
由于一般的线性基不滋磁删除向量，因此我们有两种替补方法：一种是时间戳线段树，还有一种是带删除的线性基。
"时间戳线段树" 这种算法对较难删除元素的处理较为通用，这里就不细讲了。下面着重讲一下带删除的线性基。
(不是说好的线性基不滋磁删除的吗？)
这里要明确一下，如果线性基存储的是 $m$ 维向量，这样的向量有 $n$ 个 (通常情况下，$m \ll n$，即 $m$ 远小于 $n$)，则插入是 $O \left( m^2 \right)$ 的，删除不能在 $O \left( m^2 \right)$ 时间内实现，但能在 $O \left( n m \right)$ 的时间内实现。
而在本题中，$n \sim m$，因此可以使用带删除的线性基。
具体方法是，我们对于线性基中的每个元素，以及被 "剔除在外" 的元素，记录一下它是由原来哪些向量异或而成的。说的更正式一点，就是把进行 Gauss 消元的初等矩阵 (的乘积) $\mathbf G$ 记录下来。
考虑删除原来的第 $i$ 个向量。首先，我们去寻找 "剔除在外" 的元素中有没有哪个向量 $\mathbf g$，它是组成中是含有 $i$ 的。更正式地，就是寻找在矩阵 $\mathbf G$ 中代表 "剔除在外" 的元素的对应行中，有没有第 $i$ 列为 $1$ 的。
如果存在，则我们使用这一行对其它所有行进行消元 (在 $\mathbf G$ 中)。由于它被剔除在外，因此组成它的向量的和恰为 $\mathbf 0$，因此消元过程中不会对原矩阵产生影响。
消元完毕后，矩阵 $\mathbf G$ 的第 $i$ 列只有 $\mathbf g$ 对应行为 $1$，于是直接 $\mathbf g$ 行删去即可。
如果不存在，则说明将该向量删去后，矩阵降秩 (即矩阵的秩变小了)。
因此，我们需要找到线性基中 (即存活的元素中) 是否有向量组成中含有 $i$。由于 $i$ 曾被插入线性基，因此至少有一个向量，其组成中含有 $i$。
设该向量为 $\mathbf g'$。和 "1." 类似，使用这一行对其它所有行进行消元，只不过这次不仅要在 $\mathbf G$ 中消，还要在原矩阵中消，因为该向量现在不等于 $\mathbf 0$。
消完后，矩阵 $\mathbf G$ 只有 $\mathbf g$ 对应行的第 $i$ 列为 $1$，直接删去该行即可。
但是这里要注意的是，线性基所要维护的不仅仅只是一组线性无关的向量，还要满足最高位为 $i$ 的向量在位置 $i$ 上。
因此，我们必须使用线性基中组成中含有 $i$ 的向量中最小的向量 $\mathbf g_0$，向其它向量进行消元 ("低消高")，才能保证消元完以后位置 $i$ 上的向量的最高位仍是 $i$。
于是我们对带删除的线性基的全部情况作了讨论，已经彻底解决了不带 1 操作的版本，使用 std::bitset 优化后的时间复杂度为 $O \left( \dfrac {(n + m) m q} \omega \right)$。
接下来是有操作 2 的情况。先考虑它对最终差分序列，不难发现，它所带来的影响是两次单点修改和若干个元素的直接删除。
此时，其实只要 "暴力干" 就可以了，注意不要将 $\mathbf 0$ 向量重复删除。
这是因为，容易运用均摊法证明复杂度的正确性。由于插入的向量不超过 $n + 2 q$ 个，因此被删除的向量也至多只有 $n + 2 q$ 个，因此总的复杂度还是 $O \left( \dfrac {(n + m) m q} \omega \right)$。
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 2034;
typedef std::bitset <N> bitset;
int n, m, q;
int lb[N];
bitset a[N], v[N], fr[N];
void insert(int id) {
for (int i = m - 1; i >= 0; --i)
if (v[id].test(i)) {
if (lb[i]) v[id] ^= v[lb[i]], fr[id] ^= fr[lb[i]];
else {lb[i] = id; return;}
}
}
void Xor(int id, const bitset t) {
int i, g = 0; if (t.none()) return;
for (i = 1; i <= n; ++i) if (v[i].none() && fr[i].test(id)) {g = i; break;}
if (!g)
for (i = 0; i < m; ++i) if (lb[i] && fr[ lb[i] ].test(id)) {g = lb[i], lb[i] = 0; break;}
for (i = 1; i <= n; ++i) if (i != g && fr[i].test(id)) v[i] ^= v[g], fr[i] ^= fr[g];
v[g] ^= t, insert(g);
}
int main() {
int i, op, l, r; bitset t;
std::ios::sync_with_stdio(false);
cin >> n >> m >> q;
for (i = 1; i <= n; ++i) cin >> a[i], v[i] = a[i] ^ a[i - 1], fr[i].set(i), insert(i);
for (; q; --q)
switch (cin >> op, op) {
case 1: {
cin >> l >> r >> t;
for (i = l; i <= r; ++i) a[i] ^= t;
Xor(l, t); if (r != n) Xor(r + 1, t);
break;
}
case 2: {
cin >> l >> r >> t;
Xor(l, a[l] ^ t); if (r != n) Xor(r + 1, a[r] ^ t);
for (i = r; i > l; --i) Xor(i, a[i] ^ a[i - 1]), a[i] = t;
a[l] = t; break;
}
case 3: {
for (t.reset(), i = m - 1; i >= 0; cout.put(48 | t.test(i--))) if (!t.test(i) && lb[i]) t ^= v[lb[i]];
cout << '\n';
}
}
return 0;
}
坑1：由于线性基的这一特殊性质 (用绿色标出)，因此寻找向量 $\mathbf g$ 的时候一定要从低位向高位找起。
坑2：注意删除向量时判断一下，如果是 $\mathbf 0$ 向量则直接 return;，保证复杂度。