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

Genius_Star · 2025-02-18 16:33:21 · 题解

思路：

考虑 P11620 的 trick，原序列显然可以转化为异或差分后的序列；因为原序列显然可以通过其异或差分异或出来，故所表示的基是相同的。

转化为异或差分序列后，操作相当于单点异或，还有区间赋值为 0；注意到总共有 n + q 级别的单点修改，故对于合法的区间推平操作显然也是 O(n + q) 次的。

现在我们只需要支持单点异或一个数，全局查询最大值；即需要维护一个支持删除的线性基。

离线后维护一个删除时间即可，使用 bitset 维护，时间复杂度为 O(\frac{n^3}{w})。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define bset bitset<N>
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 2020;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, q, op, l, r;
int pre[N];
bool f[N];
vector<pair<bset, int>> V[N];
bset x;
bset a[N], d[N];
pair<bset, int> p[N];
inline void insert(pair<bset, int> v){
    for(int i = m - 1; i >= 0; --i){
        if(!v.fi[i])
          continue;
        if(p[i].se == -1){
            p[i] = v;
            break;
        }
        if(p[i].se < v.se)
          swap(v, p[i]);
        v.fi ^= p[i].fi;
    }
}
inline bset ask(){
    bset ans;
    for(int i = m - 1; i >= 0; --i)
      if(!ans[i] && p[i].se != -1)
        ans ^= p[i].fi;
    return ans;
}
inline void print(bset ans){
    for(int i = m - 1; i >= 0; --i)
      putchar(ans[i] + '0');
    putchar('\n');
}
bool End;
int main(){
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        d[i] = a[i - 1] ^ a[i];
    }
    for(int i = 1; i <= q; ++i){
        op = read();
        if(op == 1){
            l = read(), r = read();
            cin >> x;
            for(int j = l; j <= r; ++j)
              a[j] ^= x;
        }
        else if(op == 2){
            l = read(), r = read();
            cin >> x;
            for(int j = l; j <= r; ++j)
              a[j] = x;
        }
        else
          f[i] = 1;
        if(op <= 2){
            for(int j = l; j <= min(r + 1, n); ++j){
                bset t = a[j] ^ a[j - 1];
                if(d[j] != t){
                    if(d[j].count())
                      V[pre[j]].push_back({d[j], i});
                    d[j] = t;
                    pre[j] = i;
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
      if(d[i].count())
        V[pre[i]].push_back({d[i], q + 1});
    for(int j = 0; j < m; ++j)
      p[j].se = -1;
    for(int i = 0; i <= q; ++i){
        for(int j = 0; j < m; ++j)
          if(p[j].se == i)
            p[j].se = -1;
        for(auto t : V[i])
          insert(t);
        if(f[i])
          print(ask());
    }
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}