Giả sử chúng ta có mảng arr các số nguyên dương và các truy vấn mảng trong đó các truy vấn [i] =[Li, Ri], đối với mỗi truy vấn, tôi tính XOR của các phần tử từ Li đến Ri (nghĩa là, arr [Li] XOR arr [Li + 1] xor ... xor arr [Ri]). Chúng ta phải tìm mảng chứa kết quả cho các truy vấn đã cho. Vì vậy, nếu đầu vào giống như - [1,3,4,8] và các truy vấn giống như [[0,1], [1,2], [0,3], [3,3]], thì kết quả sẽ là [2,7,14,8]. Điều này là do biểu diễn nhị phân của các phần tử trong mảng là - 1 =0001, 3 =0011, 4 =0100 và 8 =1000. Khi đó, các giá trị XOR cho các truy vấn là - [0,1] =1 xor 3 =2, [1,2] =3 xor 4 =7, [0,3] =1 xor 3 xor 4 xor 8 =14 và [3,3] =8
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của arr
- xác định một mảng được gọi là pre, có kích thước n + 1, sau đó điền trước, sao cho pre [i]:=pre [i - 1] XOR arr [i - 1]
- Xác định ans mảng khác
- cho tôi trong phạm vi từ 0 đến số lượng truy vấn - 1
- l:=queries [i, 0], r:=queries [i, 1]
- tăng l và r lên 1
- chèn pre [r] XOR pre [l - 1], vào ans
- trả lại ans
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[1,3,4,8] [[0,1],[1,2],[0,3],[3,3]]
Đầu ra
[2,7,14,8]