P5607 [Ynoi2013] 无力回天 NOI2017 Solution

Description

给定长为 $n$ 的序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作，分以下两种：

1. $\mathrm{modify}(l,r,k)$：对于每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i\mathrm{xor}k$
2. $\mathrm{query}(l,r,k)$：求 max ⁡ b ⊆ a l ⋯ r { b 1 ⊕ b 2 ⊕ ⋯ ⊕ b ∣ b ∣ ⊕ k } \max\limits_{b \subseteq a_{l\cdots r}} \{ b_1 \oplus b_ 2 \oplus \cdots \oplus b_{|b|} \oplus k \} b⊆al⋯r​max​{b1​⊕b2​⊕⋯⊕b∣b∣​⊕k}

Limitations

$1\le n,m\le 5\times 10^4$
$1\le l\le r\le n$
$0\le a_i,k\le 10^9$
$3\text{s},125\text{MB}$

Solution

看到区间最大异或和，想到线段树套线性基。
然后发现 $\mathrm{modify}$ 操作打不了标记，也无法暴力修改。
考虑将 $a$ 差分，设 $b_1=a_1$，$b_i=b_{i-1}\oplus a_i(i>1)$。
则 $a_i=b_1\oplus b_2\cdots \oplus b_i$。
由异或性质不难发现，从 $a_{l\cdots r}$ 中选，等价于从 $a_l,b_{l+1\cdots r}$ 中选，因此两者的线性基是等价的。

因此，线段树上只需要维护 $b$，单点修改，再用一个树状数组维护 $b$ 即可（用于求 $a_l$）。注意特判 $l=r$。

Code

$4.17\text{KB},29.66\text{s},26.27\text{MB}\text{(in total, C++ 20 with O2)}$

// Problem: P5607 [Ynoi2013] 无力回天 NOI2017
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5607
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
if(a < b){ a = b; return true; }
return false;
}

template<class T>
bool chmin(T &a, const T &b){
if(a > b){ a = b; return true; }
return false;
}

struct Basis {
    array<int, 31> a;
    Basis() {}
    
    void insert(int x) {
        for (int i = 30; i >= 0; i--) {
            if (x & (1 << i)) {
                if (a[i]) x ^= a[i];
                else {
                    a[i] = x;
                    return;
                }
            }
        }
    }
    
    void clear() {
        a.fill(0);
    }
    
    int max_xor(int v = 0) {
        for (int i = 30; i >= 0; i--) {
            if ((v ^ a[i]) > v) {
                v ^= a[i];
            }
        }
        return v;
    }
    
};

Basis operator+(const Basis& lhs, const Basis& rhs) {
    auto res = lhs;
    for (int i = 30; i >= 0; i--) {
        if (rhs.a[i]) res.insert(rhs.a[i]);
    }
    return res;
}

int lowbit(int i) { return i & -i; }
int ls(int u) { return 2 * u + 1; }
int rs(int u) { return 2 * u + 2; }

struct Tree {
    struct Node {
        int l, r;
        Basis bas;
    };
    
    int n;
    vector<Node> tr;
    vector<int> a, c;
    
    Tree() {}
    Tree(vector<int>& _a): a(_a) {
        n = a.size();
        c.resize(n);
        tr.resize(n << 2);
        
        for (int i = n - 1; i >= 1; i--) a[i] ^= a[i - 1];
        for (int i = 0; i < n; i++) add(i, a[i]);
        build(0, 0, n - 1);
    }
    
    void add(int x, int v) {
        for (int i = x + 1; i <= n; i += lowbit(i)) {
            c[i - 1] ^= v;
        }
    }
    int ask(int x) {
        int ans = 0;
        for (int i = x + 1; i; i -= lowbit(i)) {
            ans ^= c[i - 1];
        }
        return ans;
    }
    
    void pushup(int u) {
        tr[u].bas = tr[ls(u)].bas + tr[rs(u)].bas;
    }
    
    void build(int u, int l, int r) {
        tr[u].l = l;
        tr[u].r = r;
        if (l == r) {
            tr[u].bas.insert(a[l]);
            return;
        }
        
        int mid = (l + r) >> 1;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
        pushup(u);
    }
    
    void update(int u, int p, int v) {
        if (tr[u].l == tr[u].r) {
            tr[u].bas.clear();
            tr[u].bas.insert(a[p] ^= v);
            return;
        }
        
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (p <= mid) update(ls(u), p, v);
        else update(rs(u), p, v);
        pushup(u);
    }
    
    Basis query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u].bas;
        }
        
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid) return query(ls(u), l, r);
        else if (l > mid) return query(rs(u), l, r);
        else return query(ls(u), l, r) + query(rs(u), l, r);
    }
    
    void modify(int l, int r, int v) {
        add(l, v);
        update(0, l, v);
        if (r < n - 1) {
            add(r + 1, v);
            update(0, r + 1, v);
        }
    }
    
    int get(int l, int r, int v) {
        int k = ask(l);
        if (l == r) return max(k ^ v, v);
        
        auto cur = query(0, l + 1, r);
        cur.insert(k);
        return cur.max_xor(v);
    }
};

signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

int n, m;
scanf("%d %d", &n, &m);

vector<int> a(n);
for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
}

Tree tree(a);

for (int i = 0, op, l, r, v; i < m; i++) {
    scanf("%d %d %d %d", &op, &l, &r, &v);
    l--, r--;
    
    if (op == 1) tree.modify(l, r, v);
    else printf("%d\n", tree.get(l, r, v));
}

return 0;
}

原文地址：https://blog.csdn.net/sblsf/article/details/145291759

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！