Array Repetition (Codeforces 1920D)
Tags: Math, dsu

Jayden has an array $$$a$$$ which is initially empty. There are $$$n$$$ operations of two types he must perform in the given order.  Jayden appends an integer $$$x$$$ ($$$1 \leq x \leq n$$$) to the end of array $$$a$$$.  Jayden appends $$$x$$$ copies of array $$$a$$$ to the end of array $$$a$$$. In other words, array $$$a$$$ becomes $$$[a,\underbrace{a,\ldots,a}_{x}]$$$. It is guaranteed that he has done at least one operation of the first type before this. Jayden has $$$q$$$ queries. For each query, you must tell him the $$$k$$$-th element of array $$$a$$$. The elements of the array are numbered from $$$1$$$.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — the number of operations and the number of queries.The following $$$n$$$ lines describe the operations. Each line contains two integers $$$b$$$ and $$$x$$$ ($$$b \in \{1, 2\}$$$), where $$$b$$$ denotes the type of operation. If $$$b=1$$$, then $$$x$$$ ($$$1 \leq x \leq n$$$) is the integer Jayden appends to the end of the array. If $$$b=2$$$, then $$$x$$$ ($$$1 \leq x \leq 10^9$$$) is the number of copies Jayden appends to the end of the array. The next line of each test case contains $$$q$$$ integers $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq \min(10^{18}, c)$$$), which denote the queries, where $$$c$$$ is the size of the array after finishing all $$$n$$$ operations.It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$. 

Output: For each test case, output $$$q$$$ integers — answers to Jayden's queries.

Note: In the first test case: After the first operation $$$a = [1]$$$; After the second operation $$$a = [1, 2]$$$; After the third operation $$$a = [1, 2, 1, 2]$$$; After the fourth operation $$$a = [1, 2, 1, 2, 3]$$$; After the fifth operation $$$a = [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3]$$$.In the fourth test case, after all operations $$$a = [1, 2]$$$.

Sample Inputs:
4
5 10
1 1
1 2
2 1
1 3
2 3
1 2 3 4 5 6 14 15 16 20
10 10
1 3
1 8
2 15
1 6
1 9
1 1
2 6
1 1
2 12
2 10
32752 25178 3198 3199 2460 2461 31450 33260 9016 4996
12 5
1 6
1 11
2 392130334
1 4
2 744811750
1 10
1 5
2 209373780
2 178928984
1 3
2 658326464
2 1000000000
914576963034536490 640707385283752918 636773368365261971 584126563607944922 1000000000000000000
2 2
1 1
1 2
1 2

Sample Outputs:
1 2 1 2 3 1 2 3 1 3
9 8 1 3 1 3 6 3 8 8
11 11 11 10 11
1 2

Solution (Python):
def r(x):
    x = int(x)
    if x in b:
        return b[x]
    for i in a:
        x = (x - 1) % i + 1
        if x in b:
            return b[x]
for _ in range(int(input())):
    a = [0]
    b = {}
    (c, d) = map(int, input().split())
    for i in range(c):
        (d, e) = map(int, input().split())
        if a[-1] > 10 ** 19:
            continue
        if d & 1:
            a[-1] += 1
            b[a[-1]] = e
        else:
            a.append(a[-1] * (e + 1))
    a = a[::-1]
    print(str(list(map(r, input().split())))[1:-1].replace(',', ''))

Solution (Python):
def r(x):
    x = int(x)
    if x in b:
        return b[x]
    for i in a:
        x = (x - 1) % i + 1
        if x in b:
            return b[x]
for _ in range(int(input())):
    a = [0]
    b = {}
    (c, d) = map(int, input().split())
    for i in range(c):
        (d, e) = map(int, input().split())
        if a[-1] > 10 ** 19:
            continue
        if d & 1:
            a[-1] += 1
            b[a[-1]] = e
        else:
            a.append(a[-1] * (e + 1))
    a = a[::-1]
    print(str(list(map(r, input().split())))[1:-1].replace(',', ''))

Solution (Python):
t = int(input())
for qq in range(t):
    k = 0
    a = input().split()
    n = int(a[0])
    q = int(a[1])
    v = []
    f = []
    for i in range(n):
        a = input().split()
        b = int(a[0])
        x = int(a[1])
        if k <= 10 ** 18:
            if b == 1:
                f.append(x)
                k += 1
                if len(v) > 0:
                    if v[-1][0] != k - 1:
                        v.append([k, k - 1, [x]])
                    else:
                        v[-1][0] += 1
                        v[-1][1] = max(0, v[-1][1])
                        v[-1][2].append(x)
                else:
                    v.append([k, k - 1, [x]])
            else:
                k *= x + 1
    s = [int(i) - 1 for i in input().split()]
    for i in range(q):
        for j in range(len(v) - 1, -1, -1):
            if s[i] % v[j][0] >= v[j][1]:
                print(v[j][2][s[i] % v[j][0] - v[j][1]], end=' ')
                break
            else:
                s[i] = s[i] % v[j][0]
    print()