题解 P5607 【[Ynoi2013]D1T1】
诗乃
2019-11-03 20:48:22
这个题太神啦QAQ
前置芝士：线段树，线性基。
求最大异或值，不难想到线性基。由于要求维护区间信息，采用线段树维护区间线性基。
但是区间修改很棘手（想了我两个小时QAQ我好菜菜）。考虑差分，将区间修改转化为两个单点修改。接下来考虑如何在差分后的序列上求答案。
记$\oplus$为异或操作，序列$b$满足$b_i=a_i \oplus a_{i-1}$，则有：
$$a_x=b_1 \oplus b_2 \oplus b_3 \oplus ....\oplus b_x$$
不难发现，对于$a$序列的区间$[l,r]$，其中任意一种数字选选取方案都可以用$a_l,b_{l+1},b_{l+2},b_{l+3}...b_{r}$中选取若干数表示出来，即**序列$a_l,a_{l+1},...a_r$的线性基与$a_l,b_{l+1},b_{l+2},...b_{r}$相同。**
查询时，求出$b_{l+1},b_{l+2},b_{l+3}...b_{r}$的线性基和$a_l$，将$a_l$插入线性基，贪心统计答案即可。
线段树上合并两个线性基复杂度$O(log^2V)$，因此总复杂度为$O(nlognlog^2V)$。
```cpp
#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int MAXN = 50050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct XOR {
int d[30], s;
void init() {memset(d, 0, sizeof d);}
void insert(int x) {
for(int i = 29; i >= 0; --i)
if((x >> i) & 1) {
if(d[i]) x ^= d[i];
else {d[i] = x; break;}
}
}
} t[MAXN << 2]; int a[MAXN], n, m;
XOR merge(XOR a, XOR b) {
XOR res; res.init();
for(int i = 29; i >= 0; --i) if(a.d[i]) res.d[i] = a.d[i]; else res.d[i] = b.d[i];
for(int i = 29; i >= 0; --i) if(a.d[i] && b.d[i]) res.insert(b.d[i]);
res.s = a.s ^ b.s; return res;
}
void P(int u) {t[u] = merge(t[L(u)], t[R(u)]);}
void build(int u, int l, int r) {
if(l == r) {t[u].insert(t[u].s = a[l]); return;}
build(L(u), l, mid); build(R(u), mid+1, r); P(u);
}
void modify(int u, int l, int r, int p, int x) {
if(l == r) {t[u].init(), t[u].insert(t[u].s ^= x); return; }
p <= mid ? modify(L(u), l, mid, p, x) : modify(R(u), mid+1, r, p, x); P(u);
}
int finds(int u, int l, int r, int p) {
return l == r ? t[u].s : (p <= mid ? finds(L(u), l, mid, p) : finds(R(u), mid+1, r, p) ^ t[L(u)].s);
}
XOR findi(int u, int l, int r, int tl, int tr) {
if(tl <= l && r <= tr) return t[u];
if(tl > mid) return findi(R(u), mid+1, r, tl, tr);
if(tr <= mid) return findi(L(u), l, mid, tl, tr);
return merge(findi(L(u), l, mid, tl, tr), findi(R(u), mid+1, r, tl, tr));
}
int main() {
read(n); read(m); for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = n-1; i; --i) a[i+1] ^= a[i]; build(1, 1, n);
for(int opt, l, r, x; m--; ) {
read(opt); read(l); read(r); read(x);
if(opt == 1) {
modify(1, 1, n, l, x);
if(r < n) modify(1, 1, n, r+1, x);
} else {
int tmp = finds(1, 1, n, l);
if(l == r) printf("%d\n", max(x, x^tmp));
else {
XOR t = findi(1, 1, n, l+1, r); t.insert(tmp);
for(int i = 29; i >= 0; --i) x = max(x, x ^ t.d[i]);
printf("%d\n", x);
}
}
}
}
```