題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 P14359 [CSP-J 2025] 异或和

Problem Statement

題目簡述

給定長度為 nn 的非負整數序列與目標值 kk。需要選出盡可能多個互不相交的非空連續區間，使得每個區間內所有元素的按位異或和都等於 kk。

請輸出最多能選出的區間數量。

Constraints

約束條件

  • 1≤n≤5×1051 \le n \le 5 \times 10^5
  • 0≤k<2200 \le k < 2^{20}
  • 0≤ai<2200 \le a_i < 2^{20}

Example

Input 1

1
2
4 2
2 1 0 3

Output 1

1
2
解釋

可以選 [1,1][1,1] 和 [2,4][2,4]，兩段的異或和分別是 22 和 1⊕0⊕3=21 \oplus 0 \oplus 3 = 2。

Input 2

1
2
4 0
2 1 0 3

Output 2

1
1
解釋

雖然 [3,3][3,3] 與 [1,4][1,4] 的異或和都為 00，但它們相交，所以不能同時選。

思路：前綴異或 + 枚舉右維護左 + 貪心

設前綴異或和 SS 為：

Si=a1⊕a2⊕⋯⊕aiS_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i

則區間 [l,r][l,r] 的異或和為：

Sr⊕Sl−1S_r \oplus S_{l-1}

我們希望它等於 kk，所以：

Sr⊕Sl−1=kS_r \oplus S_{l-1} = k

等價於：

Sl−1=Sr⊕kS_{l-1} = S_r \oplus k

也就是固定 [l,r][l,r] 的右端點 rr，只要找到某個左端點 ll，使得前綴異或和 Sl−1=Sr⊕kS_{l-1} = S_r \oplus k，就能形成一段合法區間。

枚舉右，維護左

當右端點固定後，合法左端點的前一個位置必須對應到某個指定的前綴值。因此只要記錄每種前綴異或值最後一次出現的位置，就能 O(1)\mathcal{O}(1) 判斷目前是否能形成一段合法區間。

貪心，找到就立刻切

如果目前右端點已經能形成一段合法區間，要不要馬上選？

答案是要。

想讓段數最多，應該優先選右端點最早的合法區間。因為越早結束，留給後面的空間越大，不會讓後續選擇變差。

更具體地說，當掃描到某個位置時，這是目前能選到的最早結束合法區間。如果不選它，改等後面才切，前面空出來的部分也不能和後面的區間重疊使用，反而只會讓下一段的起點更晚或不變，不可能得到更多段。

正確性說明：交換論證

假設某個最優方案在目前已經存在合法區間時，沒有選這個最早結束的區間，而是選了之後才結束的第一段。把那一段替換成目前這段，段數不變，且第一段結束位置更早，後面的可用範圍只會變大。因此存在一個最優方案會選目前這段。於是掃描時一旦能切，就立刻切是安全的。

如何避免區間相交

用 last 記錄上一段已選區間的右邊界。當目前查到的前綴位置不在 last 之後，代表形成的區間會和上一段相交，不能選；只有左端點落在 last 之後，才是一段新的合法區間。

此外，對於固定的右端點來說，我們希望合法的左端點盡量靠右，這樣形成的區間越短，越容易避開上一段已選區間。因此只需要保留每個前綴異或值最後出現的位置即可。

核心技巧

先用前綴異或把區間條件轉成單點查詢，再用最早結束優先的貪心處理互不相交限制。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)
  • 空間複雜度：O(n)\mathcal{O}(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict

def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    ans = s = last = 0
    pos = defaultdict(lambda: float('-inf'))
    pos[0] = 0
    for r, x in enumerate(A, start=1):
        s ^= x
        if pos[s ^ k] + 1 > last:  # [pos[s ^ k] + 1, r] 是合法區間
            ans += 1
            last = r
        pos[s] = r
    print(ans)

if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @4AUB. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.