比赛场次 462
比赛名称 COGS快乐周赛
比赛状态 已结束比赛成绩
开始时间 2020-01-10 00:00:00
结束时间 2020-01-17 23:59:59
开放分组 全部用户
注释介绍
题目名称 弹飞绵羊
输入输出 bzoj_2002.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar梦那边的美好ET AAAAAAAAAA 1.473 s 18.24 MiB 100
GravatarS.H.马卡卢索 ATTTTTTTTT 9.000 s 15.18 MiB 10
GravatarreØreOré ATTTTTTTTT 9.001 s 14.42 MiB 10

弹飞绵羊

★★★☆   输入文件:bzoj_2002.in   输出文件:bzoj_2002.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

某天, Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始, Lostmonkey 在地上沿着一条直线摆上$ n $个装置,每个装置设定初始弹力系数$ k_i $,当绵羊达到第$ i $个装置时,它会往后弹$ k_i $步,达到第$ i+k_i $个装置,若不存在第$ i+k_i $个装置,则绵羊被弹飞。绵羊想知道当它从第$ i $个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey 可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

【输入格式】

第一行包含一个整数$ n $,表示地上有$ n $个装置,装置的编号从$ 0 $到$ n-1 $,接下来一行有$ n $个正整数,依次为那$ n $个装置的初始弹力系数。第三行有一个正整数$ m $,接下来$ m $行每行至少有两个数$ i,j $,若$ i = 1 $,你要输出从j出发被弹几次后被弹飞,若$ i = 2 $则还会再输入一个正整数$ k $,表示第$ j $个弹力装置的系数被修改成$ k $。对于$ 10\% $的数据$ n , m ≤ 10000 $,对于$ 100\% $的数据$ n ≤ 200000, m ≤ 100000 $

【输出格式】

对于每个$ i = 1 $的情况,你都要输出一个需要的步数,占一行。

【样例输入】

4                              
1 2 1 1						   
3
1 1
2 1 1
1 1

【样例输出】

2
3