P12827 「DLESS-2」XOR and Even

Genius_Star · 2026-11-11 08:29:55 · 题解

trick 题。

思路：

钦定必选偶数个异或的方法比较多：

• 一种是最高位添加一个 1。

• 一种是转化为 \{a_1 \oplus a_2, \cdots, a_{n - 1} \oplus a_n \}（即异或差分）上选任意个。

前者是容易证明的，但是因为添加了一位，可能在某种限制下会多一些细节，而后者和平常的线性基一样了，较为好时限一些，这里采用异或差分做法。

先证明一下正确性：

• 首先这样选出来的一定是偶数个 a_i 进行异或，因为每次要么新添两个数，要么 (a \oplus b) \oplus (b \oplus c) 把 b 消掉了。

• 然后对于任何选偶数个 a_i 的方案都可以唯一构造出来，具体的，设选了 p_1, \cdots, p_{2k}，那么配对 [p_{2i - 1}, p_{2i}]，然后选择它们区间的异或差分即可构造出它们俩来。

于是接下来只需要在普通线性基上考虑了。

第二问较为简单，异或上 x 的最大值，那么把区间线性基求出来后贪心的从高到低扫一遍即可，区间线性基可以离线下来变成前缀线性基。

再来考虑第一问，要求 \le x 的数的方案数，在线性基上，异或出任意一个可以异或出来的数的方案数都是 2^{all - siz}，即自由元任意选，此时基底唯一确认；那么只要我们求出可以异或出 \le x 的多少个数 num，那么答案就是 num \times 2^{all - siz}。

看上去是个数位 dp？实际上我们枚举钦定一下与 x 的 LCS（最长公共后缀），然后算一下贡献即可，分讨是比较复杂的，具体来说，考虑维护一个 now 表示当前 \ge i + 1 后缀与 x 相同时，线性基能表示出的一个数，然后考虑现在在枚举 i（设 s_i 表示 \le i 位有多少基底）：

• 如果线性基存在 2^i 的基底：
  • 此时若 x 当前位为 1，那么对于 now 来说，可以通过当前基底使得当前位为 0，于是前面的位任意填都是 \le x 的，贡献是 2^{s_{i - 1}}。
  • 否则 x 当前位是 0，对于 now 如果是 1 的话则异或上当前基底维持一个后缀相等。
• 否则不存在 2^i 的基底：
  • 此时若 x 当前位为 1，如果 now 当前位也是 1，那么显然无影响也无贡献产生；否则 now 当前位是 0，而且还不存在当前的基底，于是最长公共后缀最长只能枚举到这，前面的任意选，贡献 2^{s_{i - 1}}。
  • 否则 x 当前位为 0，如果 now 当前位为 1，那么最长公共后缀的枚举也只能到此为止，且不造成贡献；否则无影响也无贡献产生。

按照上面分讨直接做即可，时间复杂度是 O(n \log n) 的，离线下来的话空间复杂度可以做到 O(n) 的。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcountll(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define lowbit(x) ((x) & (-(x)))
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 5e5 + 10, M = 30, mod = 1e9 + 7;
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 T, n, q, op, l, r, x, cnt;
int a[N], b[N], ans[N], p2[N];
namespace Xor{
    int other;
    int h[M], tim[M];
    namespace BIT{
        int a[N];
        inline void init(){
            for(int i = 0; i <= n; ++i)
              a[i] = 0;
        }
        inline void add(int x, int v){
            for(int i = x; i <= n; i += lowbit(i))
              a[i] += v;
        }
        inline int ask(int x){
            int sum = 0;
            for(int i = x; i; i -= lowbit(i))
              sum += a[i];
            return sum;
        }
    }
    inline void init(){
        BIT::init();
        other = 0;
        for(int i = 0; i < M; ++i)
          h[i] = tim[i] = 0;
    }
    inline void ins(int x, int id){
        for(int i = M - 1; i >= 0; --i){
            if((x >> i) & 1){
                if(!h[i]){
                    h[i] = x;
                    tim[i] = id;
                    return ;
                }
                if(tim[i] < id){
                    swap(tim[i], id);
                    swap(h[i], x);
                }
                x ^= h[i];
            }
        }
        ++other;
        BIT::add(id, 1);
    }
    int s[M];
    inline int ask(int l, int x, bool op){
        if(op){
            for(int i = M - 1; i >= 0; --i){
                if((x >> i) & 1)
                  continue;
                if(tim[i] >= l){
                    // cerr << i << ' ' << h[i] << '\n';
                    x ^= h[i];
                }
            }
            return x;
        }
        else{
            int rother = other - BIT::ask(l - 1);
            if(!x)
              return p2[rother];
            for(int i = 0; i < M; ++i)
              s[i] = (i ? s[i - 1] : 0) + (tim[i] >= l);
            int now = 0, sum = 0;
            bool flag = 1;
            for(int i = M - 1; i >= 0; --i){
                if(tim[i] >= l){
                    if((x >> i) & 1){
                        sum = (sum + p2[i ? s[i - 1] : 0]) % mod;
                        if(((now >> i) & 1) == 0)
                          now ^= h[i];
                    }
                    else{
                        if((now >> i) & 1)
                          now ^= h[i];
                    }
                }
                else{
                    if((x >> i) & 1){
                        // cerr << i << ' ' << sum << '\n';
                        if(((now >> i) & 1) == 0){
                            sum = (sum + p2[i ? s[i - 1] : 0]) % mod;
                            flag = 0;
                            break;
                        }
                        // cerr << i << ' ' << sum << '\n';
                    }
                    else{
                        if((now >> i) & 1){
                            flag = 0;
                            break;
                        }
                    }
                }
            }
            // cerr << sum << ' ' << flag << ' ' << now << '\n';
            sum += flag;
            return 1ll * sum * p2[rother] % mod;
        }
    }
}
vector<pair<pair<int, int>, pair<int, bool>>> Q[N];
inline void solve(){
    cnt = 0;
    n = read(), q = read();
    for(int i = 1; i <= n; ++i)
      a[i] = read();
    Xor::init();
    for(int i = 1; i < n; ++i){
        b[i] = a[i] ^ a[i + 1];
        Q[i].clear();
    }
    for(int i = 1; i <= q; ++i){
        ans[i] = 0;
        op = read(), l = read(), r = read(), x = read();
        if(l == r){
            ans[i] = op ? x : 1;
            continue;
        }
        Q[r - 1].push_back({{l, x}, {i, op}});
    }
    for(int i = 1; i < n; ++i){
        Xor::ins(b[i], i);
        // cerr << "ins: " << b[i] << '\n';
        for(auto t : Q[i])
          ans[t.se.fi] = Xor::ask(t.fi.fi, t.fi.se, t.se.se);
    }
    for(int i = 1; i <= q; ++i){
        write(ans[i]);
        putchar('\n');
    }
}
inline void init(){
    p2[0] = 1;
    for(int i = 1; i < N; ++i)
      p2[i] = 2ll * p2[i - 1] % mod;
}
int main(){
    init();
    T = read();
    while(T--)
      solve();
    return 0;
}