I’m trying to solve HackersEarth/CodeMonks problem called Bit operations. Here is the problem:
You are given an array of size n. Initially, all the elements of the array are zero. You are given q queries, where each query is of the following type:
- 1 LRX: For each element in the range [L,R] like y, set y=y|X
- 2 LRX: For each element in the range [L,R] like y, set y=y&X
- 3 LRX: For each element in the range [L,R] like y, set y=y⊕X
- 4 LR: Print the sum of the elements in the range [L,R]
- 5 LR: Print the result after performing the XOR operation of the elements in the range [L,R]
I’ve used Binary Indexed tree as the problem marked under the "Tree"s category, and here is my code:
#include <iostream>
#include <vector>
using namespace std;
void update_sum(vector<int>& bit, const int idx, const int val) {
for(int i = idx; i < bit.size(); i += i & (-i)) {
bit[i] += val;
}
}
int query_sum(vector<int>& bit, int idx) {
int sum = 0;
while(idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
}
int query_element(vector<int>& bit, int idx) {
int sum = bit[idx];
if (idx > 0) {
int z = idx - (idx & -idx);
idx--;
while (idx != z) {
sum -= bit[idx];
idx -= (idx & -idx);
}
}
return sum;
}
int query_range_sum(vector<int>& bit, int left, int right) {
int left_sum = query_sum(bit, left - 1);
int right_sum = query_sum(bit, right);
return right_sum - left_sum;
}
int query_xor(vector<int>& bit, int l, int r) {
int s = r;
int _xor = query_element(bit, s);
--r;
while(r >= l) {
s = r;
_xor ^= query_element(bit, s);
--r;
}
return _xor;
}
void _xor(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] ^= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}
void _or(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] |= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}
void _and(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] &= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}
int main() {
int n = 0;
cin >> n;
int q = 0;
cin >> q;
vector<int> arr(n, 0);
vector<int> bit(n + 1, 0);
while(q--) {
int type = 0;
cin >> type;
if(type == 5) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query_xor(bit, l, r);
cout << ans << "\n";
} else if(type == 4) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query_range_sum(bit, l, r);
cout << ans << "\n";
} else if(type == 1) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_or(bit, arr, val, l, r);
} else if(type == 2) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_and(bit, arr, val, l, r);
} else if(type == 3) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_xor(bit, arr, val, l, r);
}
}
return 0;
}
But this code causes TLE on some test case. I suspect that the reason is the query_xor() function, but I can’t see some other way to get the XOR of the range [L, R] another way. Could you please help me with this TLE?
Regards.
