Problem Overview

Given an empty array a, perform n operations of two types:

• Type 1: Append a number x (1 ≤ x ≤ n) to the array.
• Type 2: Replicate the current array x times (1 ≤ x ≤ 10^9) and append the copies.

After all operations, q queries ask for the value at position k (1-indexed). Constraints: n, q ≤ 10^5, and 1 ≤ k ≤ min(10^18, final_array_size).

Approach 1: Round-Based Simulation with Binary Search

Core Insight

Group consecutive Type-1 operations followed by a Type-2 operation into a single "round". Each round follows the pattern: add elements → replicate.

Since the maximum answer is 10^18, at most 60 rounds are needed (because 2^60 > 10^18).

Data Structures

• num[i]: Total elements after completing round i
• rep[i]: Replication factor for round i (copy count + 1)
• v[i]: Vector storing newly added elements in round i

Query Resolution

Satrting from the last round, locate where position k first appears. For round i:

1. Calculate cycle length: cycle_len = num[i] / rep[i]
2. Position within cycle: t = k % cycle_len, set t = cycle_len if t == 0
3. If t <= num[i-1], the element existed before this round—recurse with k = t
4. Otherwise, the element is new in this round—return v[i][t - num[i-1] - 1]

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long num[100], rep[100];
vector<int> v[100];

long long query(long long x, int round) {
    while (true) {
        while (num[round - 1] >= x) round--;
        
        long long cycle = num[round] / rep[round];
        long long t = x % cycle;
        if (t == 0) t = cycle;
        
        if (t <= num[round - 1]) {
            x = t;
        } else {
            return v[round][t - num[round - 1] - 1];
        }
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    
    for (int i = 1; i <= 65; ++i) {
        v[i].clear();
        num[i] = 0;
        rep[i] = 1;
    }
    
    int op, x, current_round = 1;
    while (n--) {
        cin >> op >> x;
        if (num[current_round - 1] >= INF) continue;
        
        if (op == 1) {
            v[current_round].push_back(x);
            num[current_round] = num[current_round - 1] + v[current_round].size();
        } else {
            long long copies = min<long long>(x, INF / num[current_round - 1]);
            num[current_round] = (num[current_round - 1] + v[current_round].size()) * (copies + 1);
            rep[current_round] = copies + 1;
            current_round++;
        }
    }
    
    while (q--) {
        long long k;
        cin >> k;
        cout << query(k, current_round) << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Approach 2: Binary Search with Cumulative Tracking

Core Insight

Track the array size and last element after each operation. For each query, binary search to find the first operation where the array exceeds k.

Data Structures

• num[i]: Array size after operation i
• last[i]: Last element in array after operation i

Query Resolution

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const long long INF = 1e18;
long long num[N], last[N];

long long query(long long x) {
    while (true) {
        int pos = upper_bound(num + 1, num + N, x) - num;
        
        long long mod = x % num[pos - 1];
        if (mod == 0) return last[pos - 1];
        
        x = mod;
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    
    for (int i = 1; i <= n; ++i) {
        int op;
        long long x;
        cin >> op >> x;
        
        if (op == 1) {
            num[i] = num[i - 1] + 1;
            last[i] = x;
        } else {
            long long copies = num[i - 1] ? min<long long>(x, INF / num[i - 1]) : x;
            num[i] = num[i - 1] * (copies + 1);
            last[i] = last[i - 1];
        }
    }
    
    while (q--) {
        long long k;
        cin >> k;
        cout << query(k) << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Analysis

• For Type-1 operations: num[i] = num[i-1] + 1, last[i] = x
• For Type-2 operations: num[i] = num[i-1] * (copies + 1), last[i] = last[i-1]

The answer is determined by examining the remainder when dividing by the size at the previuos operation.

Complexity Comparison

Both approaches achieve O(log n) query time with careful handling of overflow and the 10^18 limit.