洛谷题目链接：弹飞绵羊
题目描述
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
输入输出格式
输入格式：
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。
接下来一行有n个正整数，依次为那n个装置的初始弹力系数。
第三行有一个正整数m，
接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。
输出格式：
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
输入输出样例
输入样例#1：
4
1 2 1 1
3
1 1
2 1 1
1 1
输出样例#1：
2
3
说明
对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
稍微解释一下题意：大概就是给出一个长度为n序列，将一只绵羊从指定位置出发，所在位置上面的数字代表它可以向后跳这么多的距离，求出从一个位置出发需要多少次才可以跳出序列。其中有修改操作。
题解：
首先我们想一下，可以通过模拟的方式来推出所需次数，但是这样很显然是会超时的。那么我们应该如何才能优化这个模拟的过程呢？
我们可以用mv[]记录一个元素需要几次才能跳出它所在的块，out[]记录跳到的下一个块上的位置，l[]，r[]记录一个块的左右端点，w[]记录向后跳的距离。
那么很显然可以得出每个元素的信息的递推式：
- 如果一个元素可以跳到下一个块上，则mv[i] = 1 , out[i] = w[i]+i;
- 如果不能跳到下一个块上，则会跳到下一个位置，此时mv[i] = mv[i+w[i]]+1，out[i] = out[i+w[i]];
然后注意一下要从后面往前推，每次修改一个元素时就重新统计这个元素所在的块就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=200000+5;
const int inf=2147483647;
int n, m, block, num;
int w[N], b[N];
int l[N], r[N];
int out[N], mv[N];
int gi(){
int ans = 0 , f = 1; char i = getchar();
while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}
while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}
return ans * f;
}
void updata(int x,int y){
for(int i=y;i>=x;i--)
if(i+w[i] > r[b[i]]) mv[i] = 1 , out[i] = i+w[i];
else mv[i] = mv[i+w[i]]+1 , out[i] = out[i+w[i]];
}
int query(int x){
int pos = x , res = 0;
while(pos <= n) res += mv[pos] , pos = out[pos];
return res;
}
int main(){
//freopen("data.in","r",stdin);
//freopen("ans.out","w",stdout);
int x, y, flag; n = gi(); block = sqrt(n);
for(int i=1;i<=n;i++) w[i] = gi();
for(int i=1;i<=n;i++) b[i] = (i-1)/block+1;
for(int i=1;i<=block;i++)
l[i] = (i-1)*block+1 , r[i] = i*block;
if(n % block) num = block+1;
else num = block;
l[num] = (num-1)*block+1 , r[num] = n;
m = gi(); updata(1,n);
for(int i=1;i<=m;i++){
flag = gi(); x = gi()+1;
if(flag == 1) printf("%d
",query(x));
else y = gi() , w[x] = y , updata(l[b[x]],r[b[x]]);
}
return 0;
}