题面
这里不再赘述了，直接搬个链接。
In Luogu
In Codeforces
思路
存储
一共两种操作：要么在末尾加一个数 x x x，要么把整一段复制 x x x 次。前一个简单，直接加上去就行了，但第二个……它复制上那么一顿，如果直接记录的话，第一爆空间，第二，查找的时候找都没法找（毕竟谁会一个个枚举呢）！
那么我们考虑第二种操作。
设原序列为 abcd \texttt {abcd} abcd，多复制 5 5 5 份，那么序列变成：
abcd abcd abcd abcd abcd abcd \texttt {abcd abcd abcd abcd abcd abcd} abcd abcd abcd abcd abcd abcd
注意：多复制 x x x 份指在原序列末尾增加 x x x 份，即序列长度变为原序列的 x + 1 x + 1 x+1 倍！
现在，我们取第 18 18 18 个数。第 18 18 18 个数是第 5 5 5 个区间的第 2 2 2 个数。但整个数列是被 copy 过的，所以……发现什么了？
第 18 18 18 个数和第 2 2 2 个数不是一个数吗！第 k k k 个区间的第 x x x 个数，跟第一个区间的第 x x x 个数，不是一样吗！
问题变简单了，序列长度大幅缩水。
但我们总要记录区间长度吧，总之你得找着这个数是谁，在哪。
所以，在每次操作的后面，我们都记录一下操作结束后序列长度，这样那么老长的序列就变为一个数字了。另外，为了优惠第一个操作，我们还要记录下每次操作完后序列的最后一个数是谁。
但是还有个问题。如果第二个操作做多了，序列长度还是会爆表，直接炸了 longlong。但好在题目的询问中只询问到 1 0 18 10^{18} 1018，所以……后面的各种内容，我们……直接扔了不要了！（好粗暴哈哈哈）
查询
存是存完了，找呢？
嘿嘿，用二分，而且是直接二分。
如果我们要查的这个数在这个区间的范围内——换句话说，就是第 k k k 次操作范围包含了第 x x x 个数，我们就返回区间数。如果不符合范围，就朝两边查找。这是一个非常基本的二分查找。
当然了，要避坑。如果查的数是第 k − 1 k - 1 k−1 个区间的末尾，就会发生奇奇怪怪的死循环。另外，在存储的时候，如果复制操作后的区间有一半超过 1 0 18 10^{18} 1018 的线了，如果整个区间全部切掉，也会导致查找区间不在存储范围内而死循环。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const ll N = 1e18;
int t , n , q;
int lst[maxn] , b;
ll sum[maxn];
//sum[i]:第i次操作结束后，序列长度
//lst[i]：第i次操作结束后，序列的最后一个数
//那么如果sum[i]>1e18，不再记录任何值（你查询区间都不到那你记它干嘛)
int cnt; //记录2操作的数量
ll ffind(ll pos , ll l , ll r) {
ll mid = (l + r) >> 1;
if(pos > sum[mid - 1] && pos <= sum[mid]) return mid;
else if(pos == sum[mid - 1]) return mid - 1;
else if(pos > sum[mid]) ffind(pos , mid + 1 , r);
else ffind(pos , l , mid);
}
int main() {
// freopen("CF1920D.in" , "r" , stdin);
// freopen("CF1920D.out" , "w" , stdout);
ios :: sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t --) {
b = 0;
cin >> n >> q;
int flag = 1;
//cout << "I'm alive!" << endl;
for(int i = 1 ; i <= n ; ++ i) {
int opt , x;
cin >> opt >> x;
if(flag && opt == 1 && sum[i - 1] + 1 <= N) {
++ b;
sum[i] = sum[i - 1] + 1;
lst[i] = x;
}
else if(flag && sum[i - 1] <= N / (x + 1)) {
++ b;
sum[i] = sum[i - 1] * (x + 1);
lst[i] = lst[i - 1];
}
else if(flag && sum[i - 1] < N) {
++ b;
sum[i] = N;
lst[i] = -1;
}
else flag = 0;
}
// cout << "!" << b << endl;
// cout << endl << endl << endl;
// for(int i = 1 ; i <= b ; ++ i) {
// cout << sum[i] << " " << lst[i] << endl;
// }
// cout << endl << endl << endl;
for(int i = 1 ; i <= q ; ++ i) {
ll k;
cin >> k;
ll cnt = ffind(k , 1 , b);
while(k != sum[cnt] || lst[cnt] == -1) {
k %= sum[cnt - 1];
if(k == 0) k = sum[cnt - 1];
cnt = ffind(k , 1 , cnt - 1);
}
cout << lst[cnt] << " ";
}
cout << endl;
}
return 0;
}