题解 P5607 【[Ynoi2013]无力回天NOI2017】

Sol1 · 2020-03-25 18:04:13 · 题解

刚学线性基……水一发吧（

首先这个题要求的是区间异或最大和，所以就可以看出来是个xxx树套线性基的做法。

又因为线性基不支持减，支持 O(\log^2 V)（其中 V 表示值域）加，所以考虑拿线段树套。

但是这个区间异或的修改就很难受……又没法直接上标记……

考虑差分，设 b_1=a_1，b_i=a_i \operatorname{xor} a_{i-1}。这样就可以把区间修改转变成单点修改了。而单点修改显然是可以 O(\log V\cdot\log N) 完成的。

然后我们再发现一个性质：a_i=b_1\operatorname{xor}b_2\operatorname{xor}b_3\operatorname{xor}\cdots\operatorname{xor}b_i。

再去考虑线性基：若有 v=a_{p_1}\operatorname{xor}a_{p_2}\operatorname{xor}\cdots\operatorname{xor}a_{p_k}，将 a 以 a_l 异或 b 的区间异或和形式代入展开，又因为 x\operatorname{xor}x\operatorname{xor}x=x，所以最后所有项都只会剩下 \leq 1 个。

所以其实就证明了 a_{[l,r]} 的线性基和 a_{l}\cup b_{[l+1,r]} 的线性基是相等的。

所以现在就可以维护 b 的线性基，每次提取出一段区间的线性基后再插入 a_l 即可。注意 l=r 要特判。

那么这道题就解决了~

最终总时间复杂度 O((N+M) \log N \log ^2 V)（话说lxl确实没几个3log的题呢），空间复杂度 O(N \log V)。

还有一个注意点就是要用另外一个数据结构（我这里用的是树状数组）来维护 b，因为要做单点修改/区间查询（因为要单点查询 a 的值，这个操作等价于在 b 上求前缀和）。这个操作显然是 O(M \log N) 的，不影响复杂度。

上代码~

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

int n, m, a[50005], c[50005];
//线性基
struct LineBase {
    int a[35];
    //往线性基里面插入一个值x
    inline void Insert(int x) {
        for (register int i = 29;~i;i--) {
            if (x & (1 << i)) {
                if (a[i]) x ^= a[i];
                else {
                    a[i] = x;
                    return;
                }
            }
        }
    }
};
//两个线性基合并
inline LineBase Merge(LineBase x, LineBase y) {
    for (register int i = 29;i >= 0;i--) {
        if (y.a[i]) x.Insert(y.a[i]);
    }
    return x;
}
//维护线性基的线段树
struct Segtree {
    LineBase nd[200005];
    //建树
    inline void Init(int p, int l, int r) {
        for (register int i = l;i <= r;i++) nd[p].Insert(a[i]);
        if (l == r) return;
        register int mid = l + r >> 1;
        Init(p << 1, l, mid);
        Init(p << 1 | 1, mid + 1, r);
        nd[p] = Merge(nd[p << 1], nd[p << 1 | 1]);
    }
    //单点修改
    inline void Modify(int p, int pl, int pr, int idx, int v) {
        if (pl == pr) {
            memset(nd[p].a, 0, sizeof(nd[p].a));//因为叶子的线性基里面只有1个数所以可以直接重构
            nd[p].Insert(a[pl] ^= v);
            return;
        }
        register int mid = pl + pr >> 1;
        if (idx <= mid) Modify(p << 1, pl, mid, idx, v);
        else Modify(p << 1 | 1, mid + 1, pr, idx, v);
        nd[p] = Merge(nd[p << 1], nd[p << 1 | 1]);
    }
    //套路区间查询
    inline LineBase Query(int p, int pl, int pr, int l, int r) {
        if (pl == l && pr == r) return nd[p];
        register int mid = pl + pr >> 1;
        if (mid >= r) return Query(p << 1, pl, mid, l, r);
        else if (mid + 1 <= l) return Query(p << 1 | 1, mid + 1, pr, l, r);
        else return Merge(Query(p << 1, pl, mid, l, mid), Query(p << 1 | 1, mid + 1, pr, mid + 1, r));
    }
};

Segtree sgt;

//用来维护差分数组的树状数组

inline int LowBit(int x) {
    return x & -x;
}

inline void Update(int i, int x) {
    for (register int j = i;j <= n;j += LowBit(j)) c[j] ^= x;
}

inline int Query(int i) {
    register int ans = 0;
    for (register int j = i;j >= 1;j -= LowBit(j)) ans ^= c[j];
    return ans;
}

inline void Read() {
    n = qread(); m = qread();
    for (register int i = 1;i <= n;i++) a[i] = qread();
}

inline void Solve() {
    for (register int i = n;i >= 2;i--) a[i] ^= a[i - 1];
    for (register int i = 1;i <= n;i++) Update(i, a[i]);
    sgt.Init(1, 1, n);
    for (register int i = 1;i <= m;i++) {
        register int opt = qread(), l = qread(), r = qread(), v = qread();
        if (opt == 1) { // 修改操作，修改位置l和位置r+1
            Update(l, v);
            sgt.Modify(1, 1, n, l, v);
            if (r < n) {
                Update(r + 1, v);
                sgt.Modify(1, 1, n, r + 1, v);
            }
        } else {//查询操作
            register int k = Query(l);//求a[l]的值
            if (l == r) {
                printf("%d\n", Max(k ^ v, v));//特判l=r的情况，这时只有2种可能，讨论即可
            } else {
                LineBase cur = sgt.Query(1, 1, n, l + 1, r);//取出线性基
                cur.Insert(k);
                //在线性基里面求最大
                for (register int i = 29;i >= 0;i--) {
                    if ((v ^ cur.a[i]) > v) v = (v ^ cur.a[i]);
                }
                printf("%d\n", v);
            }
        }
    }
}

int main() {
    Read();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}//完结撒花~