我们要询问一个区间的任意子集合 \(\oplus\) 后 \(\oplus\ v\) 的最大值, 很容易想到线段树维护线性基.
但是这里要对区间 \(\oplus\) 一个数, 不好修改, 但改为单点修改就容易了.
我们设:
-
\(b_1 = a_1\).
-
\(b_i = a_i \oplus a_{i-1}\).
那么 \(a_i = \bigoplus_{j=1}^i{b_j}\). 那对于 \(l \sim r\) 的区间 \(\oplus v\) 就是 \(b_l = b_l \oplus v\), \(b_{r+1} = b_{r+1} \oplus v\).
线性基如何维护? 因为\(a_i = \bigoplus_{j=1}^i{b_j}\), 故集合 \({a_l, b_{l+1}, \dots, b_r}\) 与集合 \({a_l,\dots, a_r}\)等价
然后就是很简单的线段树上单点修改, 区间询问, 再用线性基找最大值即可.
使用LSGT-懒标记线段树, LinearBasis-异或线性基(\(1 \sim 64\) 位).
struct tag {
uLL add;
tag() : add(0) {}
tag(uLL x) : add(x) {}
bool empty() const {
return !add;
}
void apply(const tag &o) {
return;
}
};
struct info {
uLL sum;
LinearBasis<32> lb;
info() : sum(0) {}
info(uLL x) : sum(x) { lb.insert(x); }
info operator+(const info &o) const {
info res;
res.sum = this->sum ^ o.sum;
for (int i = 0; i < 32; i++) {
if (this->lb[i])
res.lb.insert(this->lb[i]);
if (o.lb[i])
res.lb.insert(o.lb[i]);
}
return res;
}
void apply(const tag &o) {
lb = LinearBasis<32>();
sum ^= o.add;
lb.insert(sum);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<int> b(n + 1);
b[1] = arr[1];
for (int i = 2; i <= n; i++) {
b[i] = arr[i] ^ arr[i - 1];
}
LSGT<info, tag> tr(b);
while (m--) {
int opt, l, r, v;
cin >> opt >> l >> r >> v;
if (opt == 1) {
tr.modify(l, l, v);
if (r != n)
tr.modify(r + 1, r + 1, v);
} else {
if (l == r) {
auto [arrl, _] = tr.query(1, l);
cout << max<int>(arrl ^ v, v) << '\n';
} else {
auto [arrl, _] = tr.query(1, l);
auto [__, lb] = tr.query(l + 1, r);
lb.insert(arrl);
LL ans = v;
for (int i = 30; i >= 0; i--) {
if (ans >> i & 1)
continue;
if (lb[i])
ans ^= lb[i];
}
cout << ans << '\n';
}
}
}
}