e367 - 區間Xor

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個特殊的陣列 A，其中 A[0] = 0，且 A[x] = A[x-1] ^ x (x >= 1)。要求計算給定區間 [a, b] 中所有元素的 XOR 值的結果。

解題思路

由於 XOR 運算具有結合律，我們可以利用前綴 XOR 陣列來優化計算。首先，預先計算出陣列 A 的前綴 XOR 陣列 ab，其中 ab[i] 儲存 A[0] ^ A[1] ^ ... ^ A[i] 的值。然後，對於每個查詢區間 [a, b]，區間 XOR 的結果可以通過 ab[b] ^ ab[a-1] 計算得到。這樣，我們就可以避免重複計算 XOR 值，提高效率。

複雜度分析

• 時間複雜度: O(N + Q)，其中 N 是陣列 A 的大小 (10^5)，Q 是查詢次數 (7)。預處理前綴 XOR 陣列需要 O(N) 的時間，每個查詢需要 O(1) 的時間，因此總時間複雜度為 O(N + Q)。
• 空間複雜度: O(N)，因為我們需要儲存大小為 N 的前綴 XOR 陣列 ab。

程式碼

#include <iostream>
using namespace std;
int ab[100001];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int bf=0;
	for(int i=1;i<=100001;++i){
		bf^=i;
		ab[i]=ab[i-1]^bf;
	}
	int a,b;
	while(cin >> a >> b)
		cout << (ab[b]^ab[a-1]) << "\n";
}