I’m trying to solve HackersEarth/CodeMonks problem called Bit operations. Unfortunately, I can't share the link of the problem (it is unshareable, you only can unlock the next section link by solving previously given problems).
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 have tried to solve this problem via BIt and segment tree and in case of both I'm getting TLE and I got stuck on this problem.
Here is my approach using bit:
#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;
}
And here is my approach using Segment tree:
#include <iostream>
#include <vector>
using namespace std;
#define MAX_SIZE 200000
int tree[4 * MAX_SIZE];
void update_xor(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] ^= val;
} else {
int m = start + (end - start) / 2;
update_xor(2 * v, val, start, m, l, r);
update_xor(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
void update_and(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] &= val;
return;
} else {
int m = start + (end - start) / 2;
update_and(2 * v, val, start, m, l, r);
update_and(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
void update_or(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] |= val;
return;
} else {
int m = start + (end - start) / 2;
update_or(2 * v, val, start, m, l, r);
update_or(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
int query(int v, int start, int end, int l, int r) {
if(l > r) {
return 0;
}
if(start == l && end == r) {
return tree[v];
}
int m = start + (end - start) / 2;
return query(2 * v, start, m, l, min(r, m)) + query(2 * v + 1, m + 1, end, max(m + 1, l), r);
}
void query_xor(int v, int& _xor, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
_xor ^= tree[v];
return;
} else {
int m = start + (end - start) / 2;
query_xor(2 * v, _xor, start, m, l, r);
query_xor(2 * v + 1, _xor, m + 1, end, l, r);
}
}
int main() {
int n = 0;
cin >> n;
int q = 0;
cin >> q;
while(q--) {
int type = 0;
cin >> type;
if(type == 5) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int _xor = 0;
query_xor(1, _xor, 1, n, l, r);
cout << _xor << "\n";
} else if(type == 4) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query(1, 1, n, l, r);
cout << ans << "\n";
} else if(type == 1) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_or(1, val, 1, n, l, r);
} else if(type == 2) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_and(1, val, 1, n, l, r);
} else if(type == 3) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_xor(1, val, 1, n, l, r);
}
}
return 0;
}
Currently, I'm trying to optimize the segment tree-based solution by applying lazy propagation, but I couldn't find a way to use it because in the case of sum segment tree, we can use lazy propagation to calculate the parent node sum value just in this way:
void updateRange(int node, int start, int end, int l, int r, int val)
{
if(lazy[node] != 0)
{
tree[node] += (end - start + 1) * lazy[node];
if(start != end)
{
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
if(start > end or start > r or end < l)
return;
if(start >= l and end <= r)
{
tree[node] += (end - start + 1) * val;
if(start != end)
{
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val);
updateRange(node*2 + 1, mid + 1, end, l, r, val);
tree[node] = tree[node*2] + tree[node*2+1];
}
But the problem in the case of XOR, ANd OR is that we can’t write something like (end — start + 1) * val for the i-th parent node.
Could you please give me some hints?
Consider each bit separately. Can you find the contribution of each bit independently?
Consider each bit separately. Consider only what happens to the $$$i$$$th bit after an OR operation on a range $$$[l, r]$$$. If $$$i$$$th bit of $$$x$$$ is $$$0$$$, noting changes, if it is $$$1$$$, all numbers in the range has bit $$$1$$$ afterwards. So, the operation becomes a range assignment operation. Similar simplifications can be applied for AND and XOR ops. For answering queries, we only need to know the number of 1s in a range. So we may keep a segment tree for each bit.
Similar problem: https://www.spoj.com/problems/SUMSUM/en/