G73 线段树+线性基合并 P5607 [Ynoi2013] 无力回天 NOI2017

// 线段树+线性基合并 O(n*logn*logv*logv)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 50005;
int a[N], n, m;
struct Tree
{
    int p[31]; // 区间线性基
    int s;     // 区间异或和
    void clear() { memset(p, 0, sizeof p); }
    void insert(int x)
    { // 插入基
        for (int i = 30; i >= 0; --i)
            if (x >> i & 1)
            {
                if (!p[i])
                {
                    p[i] = x;
                    break;
                }
                x ^= p[i];
            }
    }
} tr[N << 2]; // 节点

Tree merge(Tree a, Tree b)
{ // 合并基
    Tree c;
    c.clear(); // 清空基数组
    for (int i = 30; i >= 0; --i)
        if (a.p[i])
            c.p[i] = a.p[i];
        else if (b.p[i])
            c.p[i] = b.p[i];
    for (int i = 30; i >= 0; --i)
        if (a.p[i] && b.p[i])
            c.insert(b.p[i]);
    c.s = a.s ^ b.s;
    return c;
}
void build(int u, int l, int r)
{ // 建树
    if (l == r)
    {
        tr[u].insert(tr[u].s = a[l]);
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    tr[u] = merge(tr[ls], tr[rs]);
}
void change(int u, int l, int r, int pos, int x)
{ // 点修
    if (l == r)
    {
        tr[u].clear(); // 清空基数组
        tr[u].insert(tr[u].s ^= x);
        return;
    }
    if (pos <= mid)
        change(ls, l, mid, pos, x);
    else
        change(rs, mid + 1, r, pos, x);
    tr[u] = merge(tr[ls], tr[rs]);
}
int sum(int u, int l, int r, int pos)
{ // 前缀和
    if (l == r)
        return tr[u].s;
    if (pos <= mid)
        return sum(ls, l, mid, pos);
    else
        return sum(rs, mid + 1, r, pos) ^ tr[ls].s;
}
Tree ask(int u, int l, int r, int L, int R)
{ // 区查
    if (L <= l && r <= R)
        return tr[u];
    if (L > mid)
        return ask(rs, mid + 1, r, L, R);
    if (R <= mid)
        return ask(ls, l, mid, L, R);
    return merge(ask(ls, l, mid, L, R), ask(rs, mid + 1, r, L, R));
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = n - 1; i; --i)
        a[i + 1] ^= a[i]; // 转成差分数组
    build(1, 1, n);
    for (int opt, l, r, v; m--;)
    {
        scanf("%d%d%d%d", &opt, &l, &r, &v);
        if (opt == 1)
        {
            change(1, 1, n, l, v); // 点修l
            if (r < n)
                change(1, 1, n, r + 1, v); // 点修r+1
        }
        else
        {
            int s = sum(1, 1, n, l); // 求a[l]
            if (l == r)
                printf("%d\n", max(v, v ^ s));
            else
            {
                Tree t = ask(1, 1, n, l + 1, r); // 求b[l+1...r]
                t.insert(s);                     // 插入a[l]
                for (int i = 30; i >= 0; --i)
                    v = max(v, v ^ t.p[i]);
                printf("%d\n", v);
            }
        }
    }
    return 0;
}