FYI — Its a Netcore Round-2 Question, contest is already over on hackerearth. =================================================================================
Text format of above photo
Given an array a, consisting of N integers. You are also given q queries on the array that you need to perform on the array a. Each query is of the following two types:
1. l r 0 - Find the or of array elements on the segment [l, r], that means the value a[l] | a[l+1] | . . . | a[r] where | is the bitwise OR operation.
2. l r x - Apply ai = ai ⊕ x for all i such that l ≤ i ≤r, where ⊕ is the bitwise XOR operation.
For each query of type 1, print the result you get.
Input format for custom testing Note: Use this input format if you are testing against custom input or writing code in a language where we don\'t provide boilerplate code.
• The first line contains an integer N denoting the length of the string.
• The seconf line contains N space-separated integers representing the array a.
• The third line contains a single integer q denoting the number of queries
• Next q lines contain 4 space-separated integers T, l, r, and x denoting a query.
Constraints
1 ≤ N, q ≤ 10^5
0 ≤ Ai, x ≤ 10^9
1 ≤ l ≤ r ≤ N
Sample input:
10
9 14 9 4 3 0 6 4 8 1
6
2 7 10 2
2 1 9 9
1 5 7 0
2 8 10 15
2 3 10 8
1 6 10 0
Sample output
15 13
Explanation
Approach
• After the 1st query, the array becomes [ 9, 14, 9, 4, 3, 0, 4, 6, 10, 3 ].
o T=2, l=7, r=10, x=2
o So, for i=[7,8,9,10], we need to perform ai = ai ⊕ x
o So, a= [9, 14, 9, 4, 3, 0, 6⊕2, 4⊕2,8⊕2, 1⊕2]
o Calculating the XOR values, we get the array a to be [ 9, 14, 9, 4, 3, 0, 4, 6, 10, 3 ].
o We can perform the other queries similarly.
• After the 2nd query, the array becomes [ 0, 7, 0, 13, 10, 9, 13, 15, 3, 3 ].
• In the 3rd query, or of the subarray [ 10, 9, 13 ] is 15.
• After the 4th query, the array becomes [0, 7, 0, 13, 10, 9, 13, 0, 12, 12 ].
• After the 5th query, the array becomes [ 0, 7, 8, 5, 2, 1, 5, 8, 4, 4 ].
• In the 6th query, the sum of the subarray [1, 5, 8, 4, 4] is 13.
Auto comment: topic has been updated by coder0687 (previous revision, new revision, compare).
Auto comment: topic has been updated by coder0687 (previous revision, new revision, compare).
sqrt decomposition would pass with good implementation i guess. Prefix sums isnt the way to go
thanks!
can you give more details to you approach, like how will you manage range updates?
The general idea of sqrt-decomposition is we divide original array into sqrt(n) pieces, each of size sqrt(n). For the last piece we can add (pow(ceil(sqrt(n)), 2)-n) "neutral" elements, lets say X, such as for any A (A operation X)==A. We precalculate answer on each piece. For range(l, r) get query, we return ((l, a1-1) OR (a1, a2) OR ... OR (ak-1, ak) OR (ak+1, r) ) where (ax, ax+1) means piece on which we have already precalculated answer, and calculate on "side" pieces manually. For range update query, we do simular thing: quickly recalculate on full pieces, and manually recalculate on sides, so time complexity is O(q sqrt n) for both queries. Not sure, but i think this is going to work for this task.
How can quick recalculation of full pieces be done? if you are asked to query a subarray of the piece you quickly recalculated it will give wrong answer since each a[i] was not modified, you can maybe use some sort of lazy update but another problem is that each piece stores the bitwise or of the piece/segment and you have to do bitiwse xor update which is a totally different operation and you cannot do xor on top of the or to give correct result directly
when we XOR all elements of some array, its OR changes like it was XOR'ed. So, we can apply XOR on precalculated OR value of subarray if it fits fully in (l; r). If it doesnt fit, for each element from l to border (or from border to r) we apply XOR and then recalculate OR of subarray
The exclusive or (xor) does not distribute over any binary function (not even itself) Wikipedia
It's wrong: 0 = (0 | 1) ^ 1 != (0 ^ 1) | (1 ^ 1) = 1
yeah, true. My bad
How can it be solved by fenwick tree? just curious
Consider the fact that the bits in any element are independent from each other under these two operations. Now you need to solve the problem for each of the $$$\log A$$$ bits, but this time the elements can only take values $$$[0,1]$$$. The operations are simply: 1. invert all bits in a range; 2. check whether there exists a $$$1$$$ in a range. The easiest way to do this is with a lazy-propagation segment tree which records the number of 1s in its range, giving complexity $$$O(n \log n \log A)$$$. Of course you could replace the segtree with sqrt decomposition since sqrt is a "stronger" structure, but I don't understand why you would want to simultaneously worsen complexity and heighten coding difficulty...
Also I don't see how you can use fenwick tree, since it only supports prefix queries.
Thanks for reply! I was just curious to know, if there is any approach other than segment-tree.
You can get rid of the $$$\log A$$$ factor by using bitwise operaitons to deal with all bits simultaneously:
For each lazy segtree node, store two values: $$$a = \text{range and}$$$ and $$$o = \text{range or}$$$.
Combining two ranges is trivial.
If you need to xor all values by $$$x$$$ in a node's range, the values update as follows (pseudocode):