这不是题解, 只是个人记录一个小知识点
起因是不知道题解里那句 "对于 (n) 个人的每个前缀，求出从后往前插入的线性基，并记录每个基是哪个人提供的，这是一个经典算法" 所指的经典算法是啥, 读了代码之后知道, 原来算法流程是这样的: 从前往后扫, 当前是第 (i) 个向量 (x) 时, 按正常插入线性基从高位往低位扫 x, 第 (j) 位遇到 (1) 时检查 (bas[j][0]) 是否为 (0), 不为 (0) 时, (bas[j][0] = x), (bas[j][1]=i); 否则, 执行 (if(ti>bas[j][1]) swap(bas[j][0],x),swap(bas[j][1],ti)), (ti) 初值为 (i), 后面正常 x^=bas[j][0], 继续扫.
意思就是说我新来一个向量 (a[i]=x), 接管了前面的 (a[k]=y) 向量对位置 (j) 的最后控制权, 但是 a[k]=x^y 可以去接管剩余的低位. 乍一看会觉得明明是 (a[i]) 提供了低位的数, 但"控制权"归 (a[k]), 这是因为 (a[k]) 通过控制第 (j) 位来间接控制了 (a[i]). 好吧可能我这段话是在放屁, 但是, emm, 反正我信了.
下面的代码是在标程基础上删了一些没必要的部分.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int bas[maxn][30][2], p[maxn], n, m, x, y, q, opt, b[maxn], w, ti, T;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &m, &p[i]);
b[i] = b[i - 1];
for (int k = 0; k < 30; k++)
bas[i][k][0] = bas[i - 1][k][0],
bas[i][k][1] = bas[i - 1][k][1];
for (int j = 1; j <= m; j++) {
scanf("%d%d", &x, &y);
b[i] ^= x;
y ^= x;
ti = i;
for (int k = 29; k >= 0; k--) {
if (!(y >> k & 1)) continue;
if (!bas[i][k][0]) {
bas[i][k][0] = y; //该位置的向量是什么
bas[i][k][1] = ti; //归哪个向量管
break;
} else {
if (bas[i][k][1] < ti)
swap(y, bas[i][k][0]), swap(ti, bas[i][k][1]);
y ^= bas[i][k][0];
}
}
}
}
for (int i = 1; i <= q; i++) {
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1)
p[x] = y;
else {
scanf("%d", &w);
w ^= b[y] ^ b[x - 1];
for (int j = 29; j >= 0; j--) {
if (!bas[y][j][0] || bas[y][j][1] <= x - 1) continue;
if ((w ^ p[bas[y][j][1]]) >> j & 1) w ^= bas[y][j][0];
}
printf("%d
", w);
}
}
}
}