题意：
https://www.lydsy.com/JudgeOnline/problem.php?id=2002
题解：
这题可以使用LCT来做，但是我不会，所以我写了分块。
如果不考虑修改，那么这题很简单，f[i]表示从第i个点弹飞所需要的次数。
如果i+ki>n那么f[i]=1否则f[i]=f[i+ki]+1。
那如果加上了修改，考虑分块，依然是f[i]，不过定义变成了，从第i个点弹出这个块所需要的次数，当然，顺便记录一下飞出这块之后到哪儿去了。
每次询问就从询问位置开始，一块一块地往前跳，反正只有根号块。每次更改就直接暴力修改这个块里的所有f[i]，一个块里最多也就根号个位置。
于是就可以在n根号n的时间复杂度之内解决这道题。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; int n,m,fk,cnt,a[200002]; typedef struct{ int s,t; }P; P p[200002]; typedef struct{ int nex,dis; }Q; Q q[200002]; int main() { scanf("%d",&n);fk=sqrt(n); for (int i=1;i<=n;) { p[++cnt].s=i;p[cnt].t=min(i+fk-1,n); i+=fk; } for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=cnt;i>=1;i--) { for (int j=p[i].t;j>=p[i].s;j--) if (j+a[j]>p[i].t) { q[j].nex=j+a[j];q[j].dis=1; } else { q[j].nex=q[j+a[j]].nex;q[j].dis=q[j+a[j]].dis+1; } } scanf("%d",&m); while(m--) { int x,y,z; scanf("%d%d",&x,&y);y++; if (x==1) { int ans=0; while(y<=n) { ans+=q[y].dis;y=q[y].nex; } printf("%d\n",ans); } else { scanf("%d",&z);a[y]=z; for (int i=1;i<=cnt;i++) if (p[i].s<=y && y<=p[i].t) { for (int j=p[i].t;j>=p[i].s;j--) if (j+a[j]>p[i].t) { q[j].nex=j+a[j];q[j].dis=1; } else { q[j].nex=q[j+a[j]].nex;q[j].dis=q[j+a[j]].dis+1; } } } } return 0; }
原文：https://www.cnblogs.com/1124828077ccj/p/12275889.html