### 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)**