[Easy] P11731 [集训队互测 2015] 最大异或和

xiezheyuan2025/2/14约 1025 字大约 5 分钟

简要题意

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$ ，满足 $0\leq a_i\leq 2^m$ ，有 $q$ 次操作，支持：

1 x y v $\forall i\in[x,y],a_i\gets a_i\oplus v$ 。
2 x y v $\forall i\in[x,y],a_i\gets v$ 。
3 询问选择 $a$ 的一个子序列，其异或和的最大值。

$1\leq n,m,q\leq 2\times 10^3$ 。

思路

首先题目中的操作三，几乎快将线性基写在题面上了，所以自然考虑线性基。

由于 $n,m,q$ 很小，所以可以考虑一些暴力的操作，例如对于操作 $1,2$ ，直接暴力完成对 $a$ 的修改，这只需要单次 $O(\frac{nm}{\omega})$ 的时间复杂度（借助 bitset）。

不过维护线性基的变化较为困难，一般来说线性基是难以支持修改的，但是可以方便的插入。而对于线性基这种无序结构来说，修改就是插入和删除。所以重点在于删除。

线性基如何支持删除一个数？这似乎很难办，不过可以离线，改为记录每个数出现的时间戳区间，用线段树分治维护。

这样询问会有 $O(nq)$ 个时间戳区间，时间复杂度 $O(\frac{nm^2q\log n}{\omega})$ 看着就很劣。

我们改为维护其差分数组的线性基，这和原本线性基是等价的。这样操作 $1$ 只会改变至多两个位置，操作 $2$ 均摊也只会改变 $O(1)$ 个位置（对于相同的差分数组，我们不更新时间戳区间）。线段树分治部分时间复杂度优化到 $O(\frac{m^2}{\omega}q\log n)$ 。略有卡常。

注意实现姿势，比如线性基撤销时只需要打一个标记，询问最大异或和用较为优秀的实现方法，这样可以跑的很快。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

const int N = 2005;
using xint = bitset<N>;
int n, m, q;
xint a[N], b[N], p[N];
bool inb[N];
stack<int> stk;

void insert(xint v){
    for(int i=m;~i;i--){
        if(!v[i]) continue;
        if(!inb[i]) return inb[i] = 1, p[i] = v, stk.push(i), void();
        v ^= p[i];
    }
}

bool operator<(const xint &a, const xint &b){
    for(int i=m;~i;i--){
        if(a[i] != b[i]) return a[i] < b[i];
    }
    return false;
}

xint max_xor(){
    xint res; res.reset();
    for(int i=m;~i;i--){
        if(!inb[i]) continue;
        if(!res[i]) res ^= p[i];
    }
    return res;
}

vector<xint> t[N << 2];

void update(int ql, int qr, const xint &v, int i, int l, int r){
    if(ql <= l && r <= qr) return t[i].emplace_back(v), void();
    if(ql <= mid) update(ql, qr, v, ls, l, mid);
    if(mid < qr) update(ql, qr, v, rs, mid + 1, r);
}

int tim[N];

void update(int p, int t, const xint &v){
    if(v == b[p]) return;
    if(b[p].any()) update(tim[p], t - 1, b[p], 1, 1, q + 1);
    tim[p] = t, b[p] = v;
}

bool tag[N];
vector<xint> answers;
int tot;

void solve(int i, int l, int r){
    size_t siz = stk.size();
    for(auto& x : t[i]) insert(x), tot++;
    if(l == r){
        if(tag[l]) answers.push_back(max_xor());
    }
    else solve(ls, l, mid), solve(rs, mid + 1, r);
    while(stk.size() > siz) inb[stk.top()] = 0, stk.pop();
}

void from_str(const string& s, xint& v){
    for(int i=0;i<m;i++) v[i] = s[m - i - 1] - '0';
}

string to_str(const xint& v){
    string res;
    for(int i=m-1;~i;i--) res += v[i] + '0';
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++){
        string s; cin >> s;
        from_str(s, a[i]);
    }
    for(int i=1;i<=n;i++) b[i] = a[i] ^ a[i - 1], tim[i] = 1;
    xint z; z.reset();
    for(int i=1;i<=q;i++){
        int op, x, y;
        cin >> op;
        if(op == 1 || op == 2){
            cin >> x >> y;
            string s; cin >> s;
            from_str(s, z);
            if(op == 1){
                for(int j=x;j<=y;j++) a[j] ^= z;
                update(x, i + 1, b[x] ^ z);
                if(y < n) update(y + 1, i + 1, b[y + 1] ^ z);
            }
            else{
                for(int j=x;j<=y;j++) a[j] = z, update(j, i + 1, a[j] ^ a[j - 1]);
                if(y < n) update(y + 1, i + 1, a[y + 1] ^ a[y]);
            }
        }
        else tag[i] = 1;
    }
    for(int i=1;i<=n;i++) update(tim[i], q + 1, b[i], 1, 1, q + 1);
    solve(1, 1, q + 1);
    for(auto& x : answers) cout << to_str(x) << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。