1. 阵列重复
题目ID：20014必做题100分
最新提交：
Wrong Answer
90 分
历史最高：
Wrong Answer
90 分
时间限制: 4000ms
空间限制: 262144kB
题目描述
有一个初始为空的序列 aa，你需要对其进行 nn 次操作，每次操作为以下两种之一：
1 x：向序列末尾加入一个正整数 xx；2 x：将序列复制 xx 份插入原序列末尾，保证之前已经进行过 11 操作。所有操作结束后有 qq 个询问，每次给定一个正整数 kk，表示询问最终序列第 kk 位的数（序列从 11 开始编号）。每个测试点 tt 组测试用例。
输入格式
每个测试由多个测试用例组成。第一行包含一个整数 tt ( 1≤t≤50001≤t≤5000 ) - 测试用例的个数。测试用例说明如下。
每个测试用例的第一行包含两个整数 nn 和 qq （ 1≤n,q≤1051≤n,q≤105 ）–操作次数和查询次数。
接下来的 nn 行描述操作。每行包含两个整数 bb 和 xx ( b∈{1,2}b∈{1,2} )( b∈{1,2}b∈{1,2} ），其中 bb 表示操作类型。如果是 b=1b=1 ，则 xx ｝( 1≤x≤n1≤x≤n ) 是杰登追加到数组末尾的整数。如果是 b=2b=2 ，那么 xx ( 1≤x≤1091≤x≤109 ) 是杰登追加到数组末尾的份数。
每个测试用例的下一行包含 qq 个整数 k1,k2,…,kqk1,k2,…,kq ( 1≤ki≤min(1018,c)1≤ki≤min(1018,c) )( 1≤ki≤min(1018,c)1≤ki≤min(1018,c) ) 表示查询，其中 cc 是完成所有 nn 操作后的数组大小。
保证所有测试用例的 nn 和 qq 之和不超过 105105 。
输出格式
对于每个测试用例，输出 qq 个整数，表示杰登询问的答案。
样例
Input 1
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
Output 1
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
数据范围
1≤t≤5000;1≤n,q,∑n,∑q≤105;1≤k≤min(1018,c)1≤t≤5000;1≤n,q,∑n,∑q≤105;1≤k≤min(1018,c)，其中 cc 为最终序列长度；对于操作 11，1≤x≤n1≤x≤n；对于操作 22，1≤x≤1091≤x≤109。
蒟蒻代码:
#include<bits/stdc++.h>
using namespace std;
const long long K=1e18;
long long t;
long long n,q;
long long use;
long long a[200005];
long long b[200005];
int main(){
scanf("%d",&t);
while(t--){
cin>>n>>q;
set<int> st;
map<int,int> mp;
use=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++){
if(use>K){
break;
}
if(a[i]==1){
use++;
mp[use]=b[i];
st.insert(use);
}
else{
if(K/use<b[i]+1){
break;
}
else{
use*=(b[i]+1);
}
}
}
while(q--){
int num;
cin>>num;
while(num){
auto lower_b=st.lower_bound(num);
if(lower_b==st.end()||(*lower_b)>num){
lower_b--;
}
if(num%(*lower_b)==0){
cout<<mp[*lower_b]<<" ";
break;
}
else{
num%=(*lower_b);
}
}
}
cout<<endl;
}
return 0;
}