PROBLEM LINK:
Problem statement:
Initially we have an empty graph and we have N(N<=2e5) queries. In each query we are given a number X(X<=1e18), which means we have to add a new node to a graph whose value is X. This node has edges to all other nodes such that bitwise XOR of value of these two nodes is a power of 2. That is the values differ in exactly one bit. Find the number of connected components after each query.
Observation:
- The number of different values that a node can connect is 60 as X<=1e18.
- If a node with value X and value Y belong to the same component then any occurrence of X and Y that comes in the query from hereon doesn’t affect the number of connected components.
Solution:
Prerequisites : DSU (Disjoint Set Union Data structure)
If X and Y differ by exactly one bit then we need to merge nodes with value X to nodes with value Y.
So if there are 1e5 occurrences of X and 1e5 occurrences of Y then we need to 1e10 merges which is intractable. So for each distinct value if we have a representative node then we connect the representative nodes alone and our answer doesn’t change due to observation-2.
The merges that is discussed in the previous paragraph is done by DSU data structure efficiently. Since our value can lie anywhere between 1 to 1e18, we need to compress them to use DSU.
- DSU merge works in log$*$N
- Co-ordinate compression takes logN
- Number of connection values is log(1e18)
Time Complexity : O(N$logNlog(1e18)log$N)