สมมติว่าเรามีอาร์เรย์ arr ของจำนวนเต็มบวกและการสืบค้นอาร์เรย์ที่การสืบค้น[i] =[Li, Ri] สำหรับการสืบค้นแต่ละครั้ง i จะคำนวณ XOR ขององค์ประกอบจาก Li ถึง Ri (นั่นคือ arr[Li] XOR arr[Li+1] xor ... xor arr[Ri] ) เราต้องหาอาร์เรย์ที่มีผลลัพธ์สำหรับข้อความค้นหาที่กำหนด ดังนั้นหากอินพุตเป็นเหมือน − [1,3,4,8] และแบบสอบถามเป็นเหมือน [[0,1],[1,2],[0,3],[3,3]] ผลลัพธ์ที่ได้ จะเป็น [2,7,14,8] เนื่องจากการแสดงไบนารีขององค์ประกอบในอาร์เรย์คือ − 1 =0001, 3 =0011, 4 =0100 และ 8 =1000 จากนั้นค่า XOR สำหรับการสืบค้นคือ − [0,1] =1 xor 3 =2 [1,2] =3 xor 4 =7, [0,3] =1 xor 3 xor 4 xor 8 =14 และ [3,3] =8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ arr
- กำหนดอาร์เรย์ที่เรียกว่า pre ขนาด n + 1 จากนั้นเติม pre เช่นว่า pre[i] :=pre[i – 1] XOR arr[i – 1]
- กำหนดอาร์เรย์อื่นและ
- สำหรับฉันอยู่ในช่วง 0 ถึงจำนวนข้อความค้นหา – 1
- l :=การสืบค้น[i, 0], r :=การสืบค้น[i, 1]
- เพิ่ม l และ r ขึ้น 1
- แทรก pre[r] XOR pre[l - 1] ลงใน ans
- คืนสินค้า
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector <int> pre(n + 1);
for(int i = 1; i <=n; i++){
pre[i] = pre[i - 1] ^ arr[i - 1];
}
vector <int> ans;
for(int i = 0; i < queries.size(); i++){
int l = queries[i][0];
int r = queries[i][1];
l++;
r++;
ans.push_back(pre[r] ^ pre[l - 1]);
}
return ans;
}
};
main(){
vector<int> v = {1,3,4,8};
vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}};
Solution ob;
print_vector(ob.xorQueries(v, v1));
} อินพุต
[1,3,4,8] [[0,1],[1,2],[0,3],[3,3]]
ผลลัพธ์
[2,7,14,8]
