题解：AT_abc457_c [ABC457C] Long Sequence
Sunrise_up
·
·
题解
求点赞 qwq！
题意
给定 n,k，和 n 个数组 a_i，数组 a_i 的长度为 l_i，以及长度为 n 的数组 l_i。还有一个初始为空的 b 数组。
## 思路
我们肯定不能直接模拟直接插入 $b$ 数组，但是我们只需求一个数 $b_k$，如果维护 $b$ 数组当前的元素个数的话，就可以知道 $b_k$ 其实是在哪一个 $a_i$ 中了。并且这样子还可以知道是 $a_i$ 中的哪个数。
假设进行第 $i$ 次操作前 $b$ 中有 $now$ 个数，显然 $\displaystyle now=\sum_{j=1}^{i-1} c_jl_j$，可以顺带统计。现在进行第 $i$ 次操作：
- 若 $k<now+c_il_i$，显然 $b_k$ 在 $a_i$ 中，那么 $b_k$ 在插入的 $c_i$ 次 $a_i$ 中是第 $k-now$ 个，于是它是 $a_i$ 中的第 $(k-now-1)\bmod l_i+1$ 个，直接输出 $a_{i,{(k-now-1)\bmod l_i+1}}$ 即可。
- 否则继续。
## 代码
时间复杂度 $\displaystyle O(\sum l_i)$，瓶颈在于输入。
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
int n,k,x,c[N],l[N],now;
vector<int> v[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>l[i];
for(int j=1;j<=l[i];j++)cin>>x,v[i].push_back(x);
}
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){
if(now+c[i]*l[i]>=k){
cout<<v[i][(k-now-1+l[i])%l[i]];
break;
}
now+=c[i]*l[i];
}
}
```