Array Repetition
Contest: Codeforces Round 919 (Div. 2)
Difficulty rating: 1900
Tags: binary search, brute force, dsu, implementation, math

Jayden has an array $$$a$$$ which is initially empty. There are $$$n$$$ operations of two types he must perform in the given order.

1. Jayden appends an integer $$$x$$$ ($$$1 \leq x \leq n$$$) to the end of array $$$a$$$.
2. 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 format:
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 format:
For each test case, output $$$q$$$ integers — answers to Jayden's queries.

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

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]$$$.

Example input:
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

Example output:
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

Editorial:
First, let's precalculate some things:
$$$$$$lst_i=\text{last element after performing the first $i$ operations}$$$$$$
$$$$$$dp_i=\text{number of elements after the first i operations}$$$$$$
We can calculate $$$dp$$$ as follows (calculating $$$lst$$$ can be done with similar reasoning):
$$$$$$dp_i= \begin{cases} dp_{i - 1} + 1 & \text{operation i is of type 1} \\ dp_{i - 1} \cdot (y + 1) & \text{operation i is of type 2} \end{cases} $$$$$$
Now, let's try answering some query $$$k$$$.
• If we have some $$$dp_i=k$$$ then the answer is $$$lst_i$$$
• Otherwise, let's find the first $$$i$$$ such that $$$dp_i >k$$$. This $$$i$$$ will be a repeat operation and our answer will lie within one of the repetitions. Our list at this point will look like:$$$$$$ \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} ... \underbrace{[l_1, \textbf{l_2},...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} $$$$$$Let the $$$k$$$-th element be the bolded $$$l_2$$$ of the final repetition. As you can see, finding the $$$k$$$-th element is equivalent to finding the $$$(k \bmod dp_{i-1})$$$-th element. Thus, we should do $$$k:=k \bmod dp_{i-1}$$$ and repeat! But there is one more case! If $$$k \equiv 0 \pmod {dp_{i-1}}$$$ then the answer is $$$lst_{i-1}$$$ (note that $$$lst_{i-1}=lst_i$$$ because $$$i$$$ is a repetition update).
Notice that after $$$\log{(\max{k})}$$$ operations of the second type, the number of elements will exceed $$$\max{k}$$$. So we only care about the first $$$\log{(\max{k})}$$$ operations of the second type. Thus, iterate through the $$$\log{(\max{a})}$$$ operations of the second type backwards and perform the casework described above. This leads to a $$$O(n+q\log{(\max{k})})$$$ solution.
There exists another slower solution that is also allowed to pass. This solution requires the observation that $$$k:=k \bmod dp_{i-1}$$$ will reduce $$$k$$$ by at least half. So the number of times we will find the first $$$i$$$ such that $$$dp_i>k$$$ and do $$$k:=k \bmod dp_{i-1}$$$ is at most $$$\log k$$$. If we repeatedly binary search for the first $$$i$$$ such that $$$dp_i \geq k$$$, and then do $$$k:=k \bmod dp_{i-1}$$$ (or stop if it's one of the other cases), then each query will take $$$O(\log n\log k)$$$ time so the total time complexity will be $$$O(n+q\log n\log {(\max{k})})$$$.