[CSP-J 2025] 异或和

GitHub 跳转原题关系图返回列表

贪心: 最大不相交区间数量, 数学: 异或区间和,异或前缀和

OJ: luogu

题目 ID: P14359

难度:普及/提高-

标签:贪心位运算前缀和

日期: 2026-02-04 09:00

前置题目

luogu P1803凌乱的yyy / 线段覆盖经典区间贪心，P14359 的核心子问题就是最大不相交区间数量

推荐练习

题意

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$ 和一个非负整数 $k$ 。定义区间 $[l, r]$ 的权值为区间内所有数的异或和。需要选出尽可能多的不相交区间，使每个区间的权值都等于 $k$ 。输出最多能选出的区间数。

样例

以样例 1 为例： $n = 4, k = 2$ ，序列 $[2, 1, 0, 3]$ 。

可以选区间 $[1, 1]$ （权值 $2$ ）和 $[2, 4]$ （权值 $1 \oplus 0 \oplus 3 = 2$ ），答案为 $2$ 。

思路

题目要求最大化不相交区间的个数，且每个区间的权值（异或和）必须等于 $k$ 。由于所有区间的权重相同（均为 1），按结束时间最早贪心是最优策略——从左到右扫描，一旦发现可以结束一个合法区间就立即选取。

前缀异或技巧：令 $pre[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i$ ，则区间 $[l, r]$ 的异或和为 $pre[r] \oplus pre[l-1]$ 。条件 $pre[r] \oplus pre[l-1] = k$ 等价于 $pre[l-1] = pre[r] \oplus k$ 。

因此，对每个右端点 $i$ ，只需检查 $pre[i] \oplus k$ 是否在当前段中出现过。配合哈希表可以在 $O(1)$ 时间内完成判断。

先看一个可以直接验证想法的正确解（ $O(n^2)$ DP，仅适合小数据）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40// 朴素 O(n²) DP 解法（用于验证小数据）
//
// 设 dp[i] 为前 i 个元素中最多能选出的不相交区间数
// 转移：
//   1. 不选以 i 结尾的区间：dp[i] = dp[i-1]
//   2. 选一个区间 [j+1, i]（异或和为 k）：dp[i] = max(dp[i], dp[j] + 1)
// 利用前缀异或 O(1) 判断区间异或和是否等于 k
// 复杂度 O(n²)，n ≤ 2000 时可接受
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5005; // 小数据规模
int n, k;
int a[maxn];
int pre[maxn]; // 前缀异或: pre[i] = a[1] ^ ... ^ a[i]
int dp[maxn];  // dp[i] = 前 i 个元素中的最优解

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] ^ a[i]; // 计算前缀异或
    }

    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1]; // 不选以 i 结尾的区间
        // 枚举左端点 j+1，区间 [j+1, i] 异或 = pre[i] ^ pre[j]
        for (int j = 0; j < i; ++j) {
            if ((pre[i] ^ pre[j]) == k) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    cout << dp[n] << "\n";
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它先列出所有异或和为 k 的候选区间，再对每个候选区间决定“选 / 不选”。递归生成完整选择后，叶子节点统一检查区间是否两两不相交，并统计答案：

另一种暴力写法：01 序列

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87// brute_01_style.cpp：01 序列风格暴力，先枚举每个候选区间选或不选。
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> a;
vector<int> prefix_xor; // prefix_xor[i] = a[1] ^ ... ^ a[i]

struct Segment {
    int l;
    int r;
};

vector<Segment> seg;
vector<int> choose_seg; // choose_seg[i] = 0/1，表示第 i 个候选区间不选/选
int answer;

bool intersect(const Segment &x, const Segment &y) {
    return max(x.l, y.l) <= min(x.r, y.r);
}

bool check() {
    for (int i = 0; i < (int)seg.size(); i++) {
        if (choose_seg[i] == 0) continue;
        for (int j = i + 1; j < (int)seg.size(); j++) {
            if (choose_seg[j] == 0) continue;
            if (intersect(seg[i], seg[j])) {
                return false;
            }
        }
    }
    return true;
}

int calc_answer() {
    int cnt = 0;
    for (int i = 0; i < (int)seg.size(); i++) {
        if (choose_seg[i] == 1) cnt++;
    }
    return cnt;
}

void dfs_choose(int dep) {
    if (dep == (int)seg.size()) {
        if (check()) {
            int value = calc_answer();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 个候选区间的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_seg[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    a.assign(n + 1, 0);
    prefix_xor.assign(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix_xor[i] = prefix_xor[i - 1] ^ a[i];
    }

    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            int value = prefix_xor[r] ^ prefix_xor[l - 1];
            if (value == k) {
                seg.push_back({l, r});
            }
        }
    }

    choose_seg.assign(seg.size(), 0);
    answer = 0;
    dfs_choose(0);

    cout << answer << '\n';
    return 0;
}

brute.cpp 的 $O(n^2)$ 瓶颈在于对每个 $i$ 都需要枚举所有 $j < i$ 。利用前缀异或的性质，我们将判断条件改写为 $pre[j] = pre[i] \oplus k$ ，从而将 $O(n^2)$ 枚举转化为 $O(1)$ 哈希查询。

具体做法：从左到右扫描，用哈希表记录当前段中出现过的所有前缀异或值。对每个位置 $i$ ：

计算 $pre = pre \oplus a_i$
查询 $target = pre \oplus k$ 是否在哈希表中
如果在，说明存在某个 $j$ 使得 $[j+1, i]$ 异或和为 $k$ → 答案加 1，清空哈希表，重置 $pre = 0$
如果不在，将 $pre$ 加入哈希表

清空哈希表有多种实现方式：

实现	清空方式	复杂度	得分
桶 + `memset`	`memset(b,0,sizeof(b))`	$O(2^{20})$ 每次	90 分 TLE
`std::map`	`b.clear()`	$O(段大小)$	100 分
时间戳数组	`cur++`	$O(1)$ 每次	100 分

最终采用时间戳数组：开一个全局数组 $vis[x]$ ，用 $vis[x] = cur$ 表示 $x$ 在当前段中出现过。清空时只需 cur++，无需遍历数组。

下面按分值逐步展开，对照学习从 $O(n^2)$ 到 $O(n)$ 的优化过程。

60 分做法

方法一： $O(n^2)$ 贪心扫描

枚举每个位置 $i$ 作为区间右端点，从 $i$ 向前倒着累加异或值，检查是否存在以 $i$ 结尾、异或和为 $k$ 的区间 $[j, i]$ 。

P1803 贪心策略是优先选结束最早的区间。以当前 $i$ 结尾的区间是当前能选到的结束最早的合法区间，一旦找到就立即选取，跳到 $i+1$ 开始新段。

60 分：$O(n^2)$ 贪心扫描

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64// 60 分做法：O(n²) 贪心扫描
// 枚举每个位置 i 作为区间右端点，从 i 向前（倒着）累加异或值，
// 检查是否存在以 i 结尾的合法区间
// P1803 贪心：优先选结束最早的区间
//
// 复杂度 O(n²)，n 较大时会超时
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,k;
int a[maxn];

void init(){
    std::cin >> n; 
    std::cin >> k;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }

}

// 计算区间 [l, r] 的异或和（直接累加，O(区间长度)）
int xor_sum(int l,int r){
    int ans = 0;
    for(int i = l;i <= r ;++i ) // i: l->r
    {
        ans = ans ^ a[i];
    }
    return ans;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int tot = 0;
    int start = 1; // 当前未分配区间的起点

    for(int i = 1;i <= n ;++i ) // 枚举区间右端点 i
    {
        bool flag = 0;
        int ans = 0;
        // 从 i 向前倒着累加异或，检查 [j, i] 的异或和是否等于 k
        for(int j = i;j>=start;j--) {
            ans = ans ^ a[j];
            if( ans == k) {
                flag = 1;
                start = i+1; // 找到就跳到下一个位置
                break;
            }
        }

        if( flag == 1) {
            tot++;
        }
    }
    std::cout << tot << "\n";
    
    return 0;
}

方法二：枚举所有合法区间 + P1803 区间贪心

利用异或性质 $a \oplus a = 0$ ，用前缀异或 $pre[r] \oplus pre[l-1]$ 快速求任意区间的异或和。

双重循环枚举所有异或和为 $k$ 的区间 $[l, r]$ ，每个合法区间看作一条线段。问题转化为经典的最大不相交区间问题（见 P1803）：按右端点从小到大排序，能选就选。复杂度 $O(n^2 + m \log m)$ ， $m$ 为合法区间数量， $n \leqslant 2000$ 时可接受。

60 分：枚举所有合法区间 + P1803 区间贪心

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73// 60 分做法（新思路）：双重循环枚举所有合法区间 + P1803 区间贪心
//
// 思路：
//   1. 利用异或性质 a^a=0，用前缀异或 pre[r] ^ pre[l-1] 快速求区间异或和
//   2. 双重 for 循环枚举所有异或和为 k 的区间 [l, r]
//   3. 把每个合法区间记为一条线段，问题转化为"最大不相交区间数量"
//   4. 按右端点排序 + 贪心选择（经典 P1803 区间贪心）
//
// 复杂度 O(n² + m log m)，其中 m 是合法区间数量，n ≤ 2000 时可接受
// 保留原 1.cpp 不动，本文件为新写法
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 5;

struct Segment {
    int l; // 区间左端点
    int r; // 区间右端点
};

int n, k;
int a[maxn];
int pre[maxn];          // pre[i] = a[1] ^ a[2] ^ ... ^ a[i]
int m;                  // 合法区间数量
Segment seg[maxn];      // 存储所有合法区间

// 按右端点从小到大排序，右端点相同时按左端点从小到大排序
bool cmp_segment(const Segment &x, const Segment &y) {
    if (x.r != y.r) {
        return x.r < y.r;
    }
    return x.l < y.l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] ^ a[i]; // 计算前缀异或
    }

    // 双重循环枚举所有合法区间
    // 利用性质：区间 [l, r] 的异或和 = pre[r] ^ pre[l-1]
    m = 0;
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            if ((pre[r] ^ pre[l - 1]) == k) {
                m++;
                seg[m].l = l;
                seg[m].r = r;
            }
        }
    }

    // 按右端点排序，贪心选择不相交区间（P1803 核心）
    sort(seg + 1, seg + m + 1, cmp_segment);

    int ans = 0;
    int last_end = 0; // 上一个已选区间的右端点
    for (int i = 1; i <= m; i++) {
        // 当前区间左端点 > 上一个已选区间的右端点，说明不重叠
        if (seg[i].l > last_end) {
            ans++;
            last_end = seg[i].r;
        }
    }

    cout << ans << '\n';
    return 0;
}

90 分做法

利用前缀异或将区间查询优化为 $O(1)$ 。用大小为 $2^{20}$ 的桶数组记录当前段中出现过的前缀异或值。每找到一个合法区间就用 memset 清空整个桶，代价 $O(2^{20})$ 每次，多次操作导致 TLE，只能得 90 分。

90 分：前缀异或 + memset 桶（TLE）

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63// 90 分做法：前缀异或 + 桶数组（memset 清空导致 TLE）
//
// 利用前缀异或性质：区间 [l, r] 的异或和 = pre[r] ^ pre[l-1]
// 条件 pre[r] ^ pre[l-1] = k 等价于 pre[l-1] = pre[r] ^ k
// 用一个大小为 2^20 的桶数组记录当前段中出现过的前缀异或值
// 每找到一个区间就用 memset 清空整个桶，代价 O(2^20)，多次操作会超时
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,k;
int a[maxn];
int b[(1<<20)+1]; // 桶数组，记录前缀异或值是否在当前段出现过

void init(){
    std::cin >> n; 
    std::cin >> k;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }

}

int xor_sum(int l,int r){
    int ans = 0;
    for(int i = l;i <= r ;++i ) // i: l->r
    {
        ans = ans ^ a[i];
    }
    return ans;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int tot = 0;
    int start = 1;

    b[0] = 1;             // 初始前缀异或 0 出现过
    int pre_sum = 0;      // 当前段内的前缀异或
    for(int i = 1;i <= n ;++i )
    {
        pre_sum = pre_sum ^ a[i];            // 更新到 i 的前缀异或
        int target = pre_sum ^ k;            // 需要的之前出现过的前缀异或值
        if( b[target] == 1) {
            // 找到了一个异或和为 k 的区间
            pre_sum = 0;
            memset(b,0,sizeof(b));            // 清空整个桶（O(2^20)，很慢）
            b[0]=1;                           // 新段初始前缀异或
            tot++;
        }
        else {
            b[pre_sum] = 1;                   // 标记当前前缀异或出现过
        }
    }
    std::cout << tot << "\n";
    
    return 0;
}

100 分做法

核心优化是避免每轮清空大数组。时间戳技术：vis[x] 记录前缀异或值 $x$ 最近一次出现的时间戳 $cur$ ，判断 vis[target] == cur 即知 $target$ 是否在当前段出现过。清空只需 cur++， $O(1)$ 。

100 分：前缀异或 + std::map

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61// 100 分做法之一：前缀异或 + std::map
//
// 和 2.cpp 思路相同，但用 std::map 代替定长桶数组
// 每找到一个区间后调用 map::clear()，复杂度 O(当前段大小)
// 在元素值范围大但段内元素较少时效率不错，但 map 单次操作 O(log size)
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,k;
int a[maxn];
std::map<int,int> b; // 用 map 记录当前段中出现过的前缀异或值

void init(){
    std::cin >> n; 
    std::cin >> k;
    for(int i = 1;i <= n ;++i )
    {
        std::cin >> a[i];
    }
}

int xor_sum(int l,int r){
    int ans = 0;
    for(int i = l;i <= r ;++i )
    {
        ans = ans ^ a[i];
    }
    return ans;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int tot = 0;
    int start = 1;

    b[0] = 1;                // 初始前缀异或 0 出现过
    int pre_sum = 0;         // 当前段内的前缀异或
    for(int i = 1;i <= n ;++i )
    {
        pre_sum = pre_sum ^ a[i];
        int target = pre_sum ^ k;  // 需要的之前出现过的前缀异或值
        if( b[target] == 1) {
            // 找到了一个异或和为 k 的区间
            pre_sum = 0;
            b.clear();             // 清空 map（O(段大小)）
            b[0]=1;                // 新段初始前缀异或
            tot++;
        }
        else {
            b[pre_sum] = 1;        // 标记当前前缀异或出现过
        }
    }
    std::cout << tot << "\n";
    
    return 0;
}

100 分：前缀异或 + 时间戳桶（最优）

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43// 100 分做法（最优）：前缀异或 + 时间戳桶
//
// 和 2.cpp 思路相同，但用「时间戳」技巧避免 memset 清空大数组
// vis[x] 记录前缀异或值 x 最近一次被"激活"的时间戳
// 每次需要清空时只需递增时间戳 cur，而非遍历整个数组
// 时间复杂度 O(n)，空间 O(2^20)
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1 << 20; // 2^20 = 1048576，a[i] 和 k 的上界
int vis[MAXV]; // 时间戳数组，vis[x] = 最近一次看到 x 的时间戳
int cur = 1;   // 当前时间戳，每找到一个区间就 +1

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    int pre = 0; // 当前段内的前缀异或和
    int ans = 0; // 答案（最多不相交区间数）
    vis[0] = cur; // 初始状态：前缀异或 0 已出现
    
    for (int i = 1; i <= n; ++i) {
        pre ^= a[i];                     // 更新前缀异或
        int target = pre ^ k;            // 需要的之前出现过的前缀异或值
        if (vis[target] == cur) {        // 在当前段内出现过 target
            ans++;                       // 找到一个合法区间
            cur++;                       // 时间戳 +1，等价于清空 vis
            pre = 0;                     // 新段的前缀异或重置
            vis[0] = cur;                // 新段初始前缀异或
        } else {
            vis[pre] = cur;              // 标记当前前缀异或已出现
        }
    }
    
    cout << ans << "\n";
    return 0;
}

代码

时间戳桶的核心思想：用一个全局 vis[] 数组和一个不断递增的 cur 代替每轮清空。

text

1
2
3
4
5
6
7
8
9
10
11
12vis[] 数组（大小为 2^20，下标为前缀异或值）
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │ ... │  x  │ ... │MAXV │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│  2  │  0  │  0  │  0  │     │  2  │     │  0  │  ← 存储最近一次被标记的 cur 值
└─↑───┴─────┴─────┴─────┴─────┴─↑───┴─────┴─────┘
  │                              │
 vis[0]=cur                    vis[x]=cur
 表示 pre=0 在当前段出现过      表示 pre=x 在当前段出现过

判断：vis[target] == cur  →  target 在当前段出现过
清空：cur++                →  所有 vis[] 值 ≠ cur，等效于全清空

以样例 [2,1,0,3], k=2 跟踪执行过程：

text

1
2
3
4
5
6
7
8初始: cur=1, vis[0]=1

 i │ a[i] │ pre │ target=pre^k │ vis[target]==cur? │ 动作
───┼──────┼─────┼──────────────┼───────────────────┼───────────────
 1 │  2   │ 2   │  2^2=0       │ vis[0]=1==cur ✓   │ ans=1, cur=2, pre=0, vis[0]=2
 2 │  1   │ 1   │  1^2=3       │ vis[3]=0≠cur      │ vis[1]=2
 3 │  0   │ 1   │  1^2=3       │ vis[3]=0≠cur      │ vis[1]=2 (已在)
 4 │  3   │ 2   │  2^2=0       │ vis[0]=2==cur ✓   │ ans=2, cur=3, pre=0, vis[0]=3

cur 递增后，旧标记自动作废，无需任何 memset 或 clear()。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45// 100 分做法：前缀异或 + 时间戳桶（最优解法）
//
// 利用前缀异或 + 贪心思想：
//   区间 [l, r] 异或和 = pre[r] ^ pre[l-1]，
//   条件 pre[r] ^ pre[l-1] = k 等价于 pre[l-1] = pre[r] ^ k。
// 从左到右扫描，用时间戳数组 vis[] 记录当前段中出现过的前缀异或值，
// 每找到一个合法区间就递增时间戳（等价于清空 vis），
// 无需 memset，O(1) 清空，总复杂度 O(n)。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1 << 20; // 2^20 = 1048576，a[i] 和 k 的上界
int vis[MAXV]; // 时间戳数组，vis[x] 记录 x 被标记的时间戳
int cur = 1;   // 当前时间戳，每找到一个区间就 +1

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int pre = 0; // 当前段内的前缀异或和
    int ans = 0; // 最多不相交区间数
    vis[0] = cur; // 初始前缀异或 0 已出现

    for (int i = 1; i <= n; ++i) {
        pre ^= a[i];                     // 计算前缀异或
        int target = pre ^ k;            // 需要的前缀异或值
        if (vis[target] == cur) {        // 在当前段中曾经出现过
            ++ans;                       // 找到一个合法区间
            ++cur;                       // 时间戳 +1 = 清空 vis
            pre = 0;                     // 新段前缀异或重置
            vis[0] = cur;                // 新段初始前缀异或
        } else {
            vis[pre] = cur;              // 标记当前前缀异或出现过
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度： $O(n)$ 。每个元素处理一次，哈希查询和更新均为 $O(1)$ 。
空间复杂度： $O(2^{20}) \approx 10^6$ 的 vis 数组，加上 $O(n)$ 的存储输入。

总结

本题是 CSP-J 2025 的题目，核心模型是单位权重区间调度 + 前缀异或哈希。关键点在于将区间异或条件转化为前缀异或的查询，再利用贪心性质从左到右扫描。实现上，时间戳技术避免了每次清空大数组的开销，是一个值得掌握的优化技巧。

核心:

贪心: 最大不相交区间数量
数学: 异或区间和,异或前缀和

P14359 [CSP-J 2025] 异或和

题目描述

小 R 有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$ 。定义一个区间 $[l, r]$ ( $1 \leq l \leq r \leq n$ ) 的权值为 $a_l, a_{l+1}, \dots, a_r$ 的二进制按位异或和，即 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ ，其中 $\oplus$ 表示二进制按位异或。

小 X 给了小 R 一个非负整数 $k$ 。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 $k$ 。两个区间 $[l_1, r_1], [l_2, r_2]$ 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 $1 \leq i \leq n$ 使得 $l_1 \leq i \leq r_1$ 且 $l_2 \leq i \leq r_2$ 。

例如，对于序列 $[2, 1, 0, 3]$ ，若 $k = 2$ ，则小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$ ，权值分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$ ；若 $k = 3$ ，则小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$ ，权值分别为 $1 \oplus 2 = 3$ 和 $3$ 。

你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

输入的第一行包含两个非负整数 $n, k$ ，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ，表示小 R 的序列。

输出格式

输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。

输入输出样例 #1

输入 #1

text

1
24 2
2 1 0 3

输出 #1

text

输入输出样例 #2

输入 #2

text

1
24 3
2 1 0 3

输出 #2

text

输入输出样例 #3

输入 #3

text

1
24 0
2 1 0 3

输出 #3

text

说明/提示

【样例 1 解释】

小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$ ，异或和分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 2 解释】

小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$ ，异或和分别为 $1 \oplus 2 = 3$ 和 $3$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 3 解释】

小 R 可以选择区间 $[3, 3]$ ，异或和为 $0$ 。可以证明，小 R 能选出的区间数量的最大值为 $1$ 。注意：小 R 不能同时选择区间 $[3, 3]$ 和区间 $[1, 4]$ ，因为这两个区间同时包含下标 $3$ 。

【样例 4】

见选手目录下的 $\textbf{\textit{xor/xor4.in}}$ 与 $\textbf{\textit{xor/xor4.ans}}$ 。

该样例满足测试点 $4, 5$ 的约束条件。

【样例 5】

见选手目录下的 $\textbf{\textit{xor/xor5.in}}$ 与 $\textbf{\textit{xor/xor5.ans}}$ 。

该样例满足测试点 $9, 10$ 的约束条件。

【样例 6】

见选手目录下的 $\textbf{\textit{xor/xor6.in}}$ 与 $\textbf{\textit{xor/xor6.ans}}$ 。

该样例满足测试点 $14, 15$ 的约束条件。

【数据范围】

对于所有测试数据，保证：

$1 \leq n \leq 5 \times 10^5$ , $0 \leq k < 2^{20}$ ;
对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i < 2^{20}$ 。

::cute-table{tuack}

测试点编号	$n \leq$	$k$	特殊性质
$1$	$2$	$=0$	A
$2$	$10$	$\leq 1$	B
$3$	$10^2$	$=0$	A
$4, 5$	^	$\leq 1$	B
$6 \sim 8$	^	$\leq 255$	C
$9, 10$	$10^3$	^	^
$11, 12$	^	$< 2^{20}$	无
$13$	$2 \times 10^5$	$\leq 1$	B
$14, 15$	^	$\leq 255$	C
$16$	^	$< 2^{20}$	无
$17$	$5 \times 10^5$	$\leq 255$	C
$18 \sim 20$	^	$< 2^{20}$	无

特殊性质 A: 对于所有 $1 \leq i \leq n$ ，均有 $a_i = 1$ 。

特殊性质 B: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 1$ 。

特殊性质 C: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 255$ 。

[CSP-J 2025] 异或和

目录

题意

样例

思路

60 分做法

方法一：O(n2)O(n^2)O(n2) 贪心扫描

方法二：枚举所有合法区间 + P1803 区间贪心

90 分做法

100 分做法

代码

复杂度

总结

方法一： $O(n^2)$ 贪心扫描