题目描述
Solution
我们注意到平时写的一般的线性基在插入的时候，$a[i]$ 所存储的值总是最靠左的那个
现在我们考虑维护每一个前缀线性基，但是 $a[i]$ 存储的值是最靠右的那一个
我们只需要对 $insert$ 稍做修改即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define maxn 1000010
using namespace std;
int n, m;
struct LinearBasis {
static const int n = 30;
int a[n + 1], p[n + 1];
void insert(int k, int v) {
for (int i = n; ~i; --i) {
if (!(v >> i & 1)) continue;
if (!a[i]) { a[i] = v; p[i] = k; break; }
if (k > p[i]) swap(a[i], v), swap(p[i], k);
v ^= a[i];
}
}
int get_max(int k) {
int v = 0;
for (int i = n; ~i; --i)
if (p[i] >= k) v = max(v, v ^ a[i]);
return v;
}
} a[maxn];
int lans;
inline void solve_0() {
int x, y; cin >> x >> y;
x = (x ^ lans) % n + 1; y = (y ^ lans) % n + 1;
if (x > y) swap(x, y);
cout << (lans = a[y].get_max(x)) << "\n";
}
inline void solve_1() {
int x; cin >> x; x ^= lans;
for (int i = 0; i <= LinearBasis::n; ++i) {
a[n + 1].a[i] = a[n].a[i];
a[n + 1].p[i] = a[n].p[i];
} ++n, a[n].insert(n, x);
}
void work() {
cin >> n >> m; lans = 0;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
for (int j = 0; j <= LinearBasis::n; ++j) {
a[i].a[j] = a[i - 1].a[j];
a[i].p[j] = a[i - 1].p[j];
}
a[i].insert(i, x);
}
for (int i = 1; i <= m; ++i) {
int opt; cin >> opt;
if (!opt) solve_0();
else solve_1();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|