AcWing 5726. 连续子序列

5726. 连续子序列 - AcWing题库

01trie 的不错的练习题。题目说了求一段连续子序列的异或和，因为异或有结合律，所以我们可以直接预处理一个前缀异或和，即 \(a[l,r] = sum[r] \operatorname {xor} sum[l - 1]\)。然后求一段异或和就变成了求任意两个 \(sum\) 的异或和，而这就可以用到 01trie。而这不是求最大值，是统计数量。在 trie 上，如果此路径上异或和大于 \(x\) 那么之后就没必要再走了，直接加上这个子树上节点数量即可。有一说一，搞了我半天。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 1000010 * 32;

int n, m;
int tr[N][2], idx, cnt[N];
int sum[N];
LL maxv; // 注意开longlong 总共数量可能会有 10 ^ 12 个

void insert(int x)
{
    int p = 0;
    for (int i = 29; i >= 0; i -- )
    {
        int s = x >> i & 1;
        if (tr[p][s] == 0) tr[p][s] = ++ idx;
        p = tr[p][s];
        cnt[p] ++ ;
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 29; i >= 0; i -- )
    {
        int s = x >> i & 1, v = m >> i & 1;
        if (!v) res += cnt[tr[p][s ^ 1]];
        p = tr[p][v ^ s];
        if (p == 0) break;
    }
    res += cnt[p];
    return res;
}


int main()
{
    cin >> n >> m;
    
    
    insert(0); // 边界上一段也要统计。
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &sum[i]);
        sum[i] ^= sum[i - 1]; // 异或前缀和，实际上用一个 s 变量就够了，或者滚动数组
        
        maxv += query(sum[i]);
        insert(sum[i]);
    }
    
    cout << maxv << endl;
    
    return 0;
}