Full Binary Tree Queries (Codeforces 960D)
Tags: Implement, 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:  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). 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). 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: 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: For each query of type 3, print the values of all nodes encountered in descending order.

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:   

Sample Inputs:
5
3 12
1 2 1
3 12
2 4 -1
3 8

5
3 14
1 5 -3
3 14
1 3 1
3 14

Sample Outputs:
12 6 3 1
12 6 2 1
8 4 2 1

14 7 3 1
14 6 3 1
14 6 2 1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
q = int(input())
l = 60
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
s = [0] * (l + 1)
ans = []
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] <= 2:
        (x, k) = t[1:]
        i = x.bit_length() - 1
        k %= pow2[i]
        s[i] = (s[i] + k) % pow2[i]
        if t[0] == 2:
            for j in range(i + 1, l):
                k *= 2
                s[j] = (s[j] + k) % pow2[j]
    else:
        x = t[1]
        ans0 = [x]
        for i in range(x.bit_length() - 1, 0, -1):
            u = (s[i] + ans0[-1] - pow2[i]) % pow2[i]
            v = u // 2
            ans0.append((v - s[i - 1]) % pow2[i - 1] + pow2[i - 1])
        ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
q = int(input())
l = 60
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
s = [0] * (l + 1)
ans = []
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] <= 2:
        (x, k) = t[1:]
        i = x.bit_length() - 1
        k %= pow2[i]
        s[i] = (s[i] + k) % pow2[i]
        if t[0] == 2:
            for j in range(i + 1, l):
                k *= 2
                s[j] = (s[j] + k) % pow2[j]
    else:
        x = t[1]
        ans0 = [x]
        for i in range(x.bit_length() - 1, 0, -1):
            u = (s[i] + ans0[-1] - pow2[i]) % pow2[i]
            v = u // 2
            ans0.append((v - s[i - 1]) % pow2[i - 1] + pow2[i - 1])
        ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline
shift = [0] * 60

def find(x):
    lvl = 0
    while 1 << lvl + 1 <= x:
        lvl += 1
    return lvl
for _ in range(int(input())):
    q = [int(i) for i in input().split()]
    x = q[1]
    lvl = find(x)
    ln = 1 << lvl
    if q[0] == 1:
        shift[lvl] = (shift[lvl] + q[2]) % ln
    elif q[0] == 2:
        shift[lvl] = (shift[lvl] + q[2]) % ln
        it = 1
        lvl += 1
        while lvl < 60:
            cur = 1 << it
            shift[lvl] = (shift[lvl] + q[2] * cur) % (1 << lvl)
            lvl += 1
            it += 1
    else:
        ind = x - (1 << lvl)
        ind_shift = (ind + shift[lvl]) % ln
        v = ln + ind_shift
        ans = [ind + ln]
        while v != 1:
            v //= 2
            lvl -= 1
            ln //= 2
            ind = v - ln
            ind_shift = (ind - shift[lvl]) % ln
            ans.append(ln + ind_shift)
        print(*ans)