Full Binary Tree Queries
Contest: Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined)
Difficulty rating: 2100
Tags: brute force, implementation, trees

You have a full binary tree having infinite levels.

Each node has an initial value. If a node has value x, then its left child has value 2·x and its right child has value 2·x + 1.

The value of the root is 1.

You need to answer Q queries.

There are 3 types of queries:

1. Cyclically shift the values of all nodes on the same level as node with value X by K units. (The values/nodes of any other level are not affected).
2. Cyclically shift the nodes on the same level as node with value X by K units. (The subtrees of these nodes will move along with them).
3. Print the value of every node encountered on the simple path from the node with value X to the root.

Positive K implies right cyclic shift and negative K implies left cyclic shift.

It is guaranteed that atleast one type 3 query is present.

Input format:
The first line contains a single integer Q (1 ≤ Q ≤ 105).

Then Q queries follow, one per line:

- Queries of type 1 and 2 have the following format: T X K (1 ≤ T ≤ 2; 1 ≤ X ≤ 1018; 0 ≤ |K| ≤ 1018), where T is type of the query.
- Queries of type 3 have the following format: 3 X (1 ≤ X ≤ 1018).

Output format:
For each query of type 3, print the values of all nodes encountered in descending order.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
Following are the images of the first 4 levels of the tree in the first test case:

Original:

After query 1 2 1:

After query 2 4 -1:

Example input:
5
3 12
1 2 1
3 12
2 4 -1
3 8

Example output:
12 6 3 1
12 6 2 1
8 4 2 1

Example input:
5
3 14
1 5 -3
3 14
1 3 1
3 14

Example output:
14 7 3 1
14 6 3 1
14 6 2 1

Editorial:
Let us define the root of the tree to be at level L = 1.
Now, the level L for any value X can be found using this formula: L = 64 -  (Number of leading unset bits in X). In C++, you can conveniently calculate the leading unset bits by using __builtin_clzll(X).
Let us imagine each level of the tree as an array AL. Observe that we only need to consider L upto 60 due to the constraint that X ≤ 1018.
• Queries of type 1 are equivalent to performing a cyclic shift of K on array AL.
• Queries of type 2 are equivalent to performing a cyclic shift of K on array AL , 2·K on array AL + 1 , 22·K on array AL + 2 ... 2Z·K on array AL + Z and so on. Since we only care about the first 60 levels, 0 ≤ Z ≤ 60 - L.
Now,we can store the net shift SL of each level. Note that, for level L, we calculate SL under modulo 2L - 1 because there are exactly 2L - 1 values in some AL.
Finally, to answer queries of type 3, do the following:
1. Let the original index(0-indexed) of X in AL be P (P = X - 2L - 1). The new index after the shift will be $$\bar{p}$$ $$( ( P + S _ { L } ) \bmod 2 ^ { L - 1 } + 2 ^ { L - 1 } ) \bmod 2 ^ { L - 1 }$$. The original value at this index was $$V = 2^{L-1} + \bar{P}$$. We can find the parent of this value in the original tree by dividing V by 2 (Integer Division).Thus, We can now find all the values in the path from V to the root in the original tree. To get the values in the current tree, we just apply the opposite shift at each level to find the value and print it.
2. Let the original value at index P in AL at some level L be V. The current value at this position after the shift will be the same as the value at index $$\bar{p}$$ $$((P + S_L \cdot -1) \bmod 2^{L-1} + 2^{L-1}) \bmod 2^{L-1}$$ in the original array. Let this value be Z. Now,$$Z = 2^{L-1} + \bar{P}$$. Print Z and set V = V / 2.
3. Repeat Step 2 and stop when V = 0.
Complexities of:
• Query 1: O(1).
• Query 2: O(60).
• Query 3: O(60).
• Overall: O(60·Q)
Refer to the code for further understanding.