Problem Link : Three Wise Men
Contest :RECode9.0
Author : conan_0
Editorailist : conan_0
DIFFICULTY :
Easy-Medium
PREREQUISITE :
Euler tour, Segment Trees with Lazy propagation, Bit-Manipulation
PROBLEM :
Update sub-tree with a particular XOR and find values of queries on sub-trees. Queries involve,
\&(a_i | a_j) and |(a_i \& a_j) where index i, j belong to given node’s sub-tree and i, j are distinct.
EXPLANATION :
There are queries on sub-tree so to perform queries efficiently we would need to convert the given tree to segment tree where contiguous indices belong to a particular sub-tree. We perform DFS and through Euler tour and convert the tree to segment tree. We maintain two segment trees:
-
To count the total number of nodes in a sub-tree.
-
A 2D Segment tree to maintain the count of 1’s in a given range of sub-tree at each bit position.
Now to perform Queries of first type, we solve for each bit individually, if bit at that position in val is 1 we need to invert all the bit at that position in whole sub-tree otherwise if bit in val is 0 bit in that position of sub-tree remains unchanged. So to invert a bit all 0’s becomes 1’s and all 1’s becomes 0’s. Updating second segment tree for count of 1’s, we can simply do this by finding the difference between count of nodes in sub-tree and count of 1’s in that sub-tree (i.e. equal to the count of 0’s before inversions). Obviously we will have to update a range of values in segment tree and we use lazy propagation for quick operations.
Performing Query of type 2, we have to find bitwise AND of all bitwise OR pairs in sub-tree, let’s consider the problem for each individual bit, for a particular bit if in a sub-tree there are 2 or more 0’s then there would be atleast 1 OR pair that would be 0 and independent of other bitwise OR pairs, bitwise AND with all other pairs will be 0. We can count the number of 0’s in sub-tree by subtracting count of 1’s in sub-tree (using second segment tree) from count of nodes in sub-tree(using first segment tree). We can develop answer for each bit individually and combine the result for each bit to obtain the final answer.
Performing Query of type 3, we have to find bitwise OR of all bitwise AND pairs in sub-tree, let’s consider the problem for each individual bit, for a particular bit if in a sub-tree there are 2 or more 1’s then there would be atleast 1 AND pair that would be 1 and independent of other bitwise AND pairs, bitwise OR with all other pairs will be 1. We can count number of 1’s in sub-tree directly from second segment tree . We can develop answer for each bit individually and combine the result for each bit to obtain the final answer.
TIME COMPLEXITY :
O(32* q*log(n) )
SOLUTION :