【分块】[LUOGU 弹飞绵羊] 分块

本文主要是介绍【分块】[LUOGU 弹飞绵羊] 分块，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题目链接：[LUOGU 弹飞绵羊]
题解：
这个题就是一个LCT的模板题，但是呢，作为一个菜鸡，LCT，，还是不会的了，那我就好好写分块吧，就好好写分块就好了，，，，

这个题用分块的写法就是比较简单了，开两个数组记录一下就好了，一个是记录这只绵羊跳多少步才能跳出他自己所在的块，再开一个记录一下他跳出去之后跳到了哪个点上就好。这样的话就很好去用分块进行维护了。，，

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=2e5+7;
const int pool=400;
int n,m,block,num,a[sea],belong[sea],l[pool],r[pool],id[sea],stp[sea];
int ask(int x){int s=0;while(1)
{s+=stp[x];if(!id[x])break;x=id[x];} return s;}
int main()
{n=read(); block=sqrt(n); num=n/block;if(n%block) num++;for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=block*i; r[num]=n;for(int i=n;i>0;i--){if(i+a[i]>n) stp[i]=1;else if(belong[i]==belong[i+a[i]]) stp[i]=stp[i+a[i]]+1,id[i]=id[i+a[i]];else stp[i]=1,id[i]=i+a[i];}m=read();for(int i=1;i<=m;i++){int s=read(),x=read(),z; x++;if(s==2){z=read(); a[x]=z;for(int i=x;i>=l[belong[x]];i--)if(belong[i]==belong[i+a[i]]) stp[i]=stp[i+a[i]]+1,id[i]=id[i+a[i]];else stp[i]=1,id[i]=i+a[i];}else printf("%d\n",ask(x));}return 0;
}