描述
题解
看到这个题,有些懵逼,没有做过类似的问题,看到讨论去有人说二分,没想通,又看到有人说离线处理,很不好意思,我概念不行,一直不懂啥叫离线,啥叫在线,于是问了问学姐,学姐说离线就是读入所有数据后再处理,而在线就是边读入边处理~如梦初醒,原来并不是什么高深的概念,我们平时做题经常用到,只是自己不知道而已。
顺着讨论区的提示,尝试着搞出来了。先将所有的操作信息都读入,存一个pos[]
数组表示每个操作处理后序列的长度。然后开始查询操作,利用二分查找ans
位置对应的指令,如果指令为1,那么就直接输出,否则截去前缀,求得对应位置的数在前缀中的位置,接着向前检索即可~~~直到检索到操作指令为1的指令,然后输出并跳出(这个合法的指令一定存在)。
代码
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int n;
ll pos[MAXN]; // 存储每个操作后的长度(位置)
struct ope
{
int val;
int oper; // 当前命令
int x; // 命令1:添加的数字
int li; // 命令2:前缀的长度
int ci; // 复制的次数
} op[MAXN];
void input()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &op[i].oper);
if (op[i].oper == 1)
{
scanf("%d", &op[i].val);
pos[i] = pos[i - 1] + 1;
}
else
{
scanf("%d%d", &op[i].li, &op[i].ci);
pos[i] = pos[i - 1] + op[i].li * op[i].ci;
}
}
}
void solve()
{
int i, k;
ll ans;
scanf("%d", &k);
for (i = 1; i <= k; i++)
{
scanf("%lld", &ans);
// 不断向前检索ans位置的对应的指令,如果是1直接输出,否则继续向前检索
while (true)
{
int p = (int)(lower_bound(pos + 1, pos + n, ans) - pos);
if (op[p].oper == 1)
{
printf("%d ", op[p].val);
break;
}
else
{
ans = ans - pos[p - 1]; // 截去前缀
ans = ans % op[p].li;
if (ans == 0)
{
ans = op[p].li;
}
}
}
}
return ;
}
int main()
{
input();
solve();
return 0;
}