OI Problems   关于

#oxvum6. 弹飞绵羊

时间限制:1 s       空间限制:125 MiB       标签: 递推 分块 省选 湖南 2010 缺题解 

算法难度等级:0       思维难度等级:0       实现难度等级:0


本题来源于:湖南 2010 年省队选拔

题目描述

某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。

游戏一开始,Lostmonkey 在地上沿着一条直线摆上 nn 个装置,每个装置设定初始弹力系数 kik_i,当绵羊达到第 ii 个装置时,它会往后弹 kik_i 步,达到第 i+kii+k_i 个装置,若不存在第 i+kii+k_i 个装置,则绵羊被弹飞。

绵羊想知道当它从第 ii 个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey 可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

输入格式

第一行包含一个整数 nn,表示地上有 nn 个装置,装置的编号从 0n10 \sim n-1

接下来一行有 nn 个正整数,依次为那 nn 个装置的初始弹力系数。

第三行有一个正整数 mm,表示操作次数。接下来 mm 行每行至少有两个数 i,ji,j

  • i=1i=1,你要输出从 jj 出发被弹几次后被弹飞

  • i=2i=2,则还会再输入一个正整数 kk,表示第 jj 个弹力装置的系数被修改成 kk

输出格式

对于每个 i=1i=1 的操作,输出一行一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
3

提示

【数据范围】
对于 20%20\% 的数据,1n,m1041 \le n,m \le 10^4
对于 100%100\% 的数据,1n2×1051\le n \le 2\times 10^51m1051\le m \le 10^5