题解 P5607 【[Ynoi2013]D1T1】

· · 题解

这个题太神啦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)。

#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);
            }
        }
    }
}