某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
这道题大致分为两种方法：动态树和分块。 因为我只是个小渣渣，只会分块做法。 首先把这n个装置分成 n√ 个块，每个块 n√ 个装置，这里不多说，分块的基础。 首先我们预处理出从每个点跳出自己属于的块，主要这里要用 O(n) 来处理，不可以用 O(nn√) ，否则会超时。
O（n）预处理 for(int i=n-1;i>=0;i--) { if(belong[a[i]+i]!=belong[i]) { fly[i][0]=1; fly[i][1]=a[i]+i; } else { fly[i][0]=fly[a[i]+i][0]+1; fly[i][1]=fly[a[i]+i][1]; } }剩下就简单了， 当修改某个点时，将它所在的块中，将它前面的可以飞到它的点修改。 查询就直接一块一块地往后飞就可以了。
#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> const int maxlongint=2147483647; const int mo=1000000007; const int N=200005; using namespace std; int part[500][2],tot,size,n,m,a[N],belong[N],fly[N][2],j,ans; int preblock() { size=sqrt(n); for(int i=0;i<=n-1;i+=size) { part[++tot][0]=i; if(i+size-1>n-1) part[tot][1]=n-1; else part[tot][1]=i+size-1; } for(int i=1;i<=tot;i++) for(int j=part[i][0];j<=part[i][1];j++) belong[j]=i; } int main() { scanf("%d",&n); preblock(); int x,y,z; for(int i=0;i<=n-1;i++) scanf("%d",&a[i]); for(int i=n-1;i>=0;i--) { if(belong[a[i]+i]!=belong[i]) { fly[i][0]=1; fly[i][1]=a[i]+i; } else { fly[i][0]=fly[a[i]+i][0]+1; fly[i][1]=fly[a[i]+i][1]; } } scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x==2) { scanf("%d",&z); a[y]=z; for(j=y;j>=part[belong[y]][0];j--) { if(belong[a[j]+j]!=belong[j]) { fly[j][0]=1; fly[j][1]=a[j]+j; } else { fly[j][0]=fly[a[j]+j][0]+1; fly[j][1]=fly[a[j]+j][1]; } } } else { ans=0; while(y<=n-1) { ans+=fly[y][0]; y=fly[y][1]; } printf("%d\n",ans); } } }