Problem Link : Three Wise Men
Contest :RECode9.0
Author : conan_0
Editorailist : conan_0
DIFFICULTY :
EasyMedium
PREREQUISITE :
Euler tour, Segment Trees with Lazy propagation, BitManipulation
PROBLEM :
Update subtree with a particular XOR and find values of queries on subtrees. Queries involve,
\&(a_i  a_j) and (a_i \& a_j) where index i, j belong to given node’s subtree and i, j are distinct.
EXPLANATION :
There are queries on subtree so to perform queries efficiently we would need to convert the given tree to segment tree where contiguous indices belong to a particular subtree. 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 subtree.

A 2D Segment tree to maintain the count of 1’s in a given range of subtree 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 subtree otherwise if bit in val is 0 bit in that position of subtree 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 subtree and count of 1’s in that subtree (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 subtree, let’s consider the problem for each individual bit, for a particular bit if in a subtree 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 subtree by subtracting count of 1’s in subtree (using second segment tree) from count of nodes in subtree(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 subtree, let’s consider the problem for each individual bit, for a particular bit if in a subtree 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 subtree 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 :