弹飞绵羊题解：
思路：
先注意一下装置编号是0到n-1，坑了我半天
先思考为什么可以用分块做？
总所周知，要是我不存在修改操作的话，我直接o(1)就结束了。
具体做法的话，就是从后往前扫一遍，cnt[u]=cnt[to]+1。然后直接查询就好了，特别地，直接跳出去的cnt[i]=1。
但是呢，涉及了修改操作。
如果像上面这么做的话，我修改一个位置，可能会对前面的很多地方都会有影响，强制更新的话就有可能到n方的强度。
我们想平衡修改和查询的复杂度，就可以往分块去想了。
对于查询而言，每次跳跃块，总共在根号n的样子。那么这里用时n根号n。
由于我维护的是：跳出块的次数，因此这样分块后修改，只会对块内有影响（在他后面的本来就不影响，在它前面的虽然总次数改变了，但是跳出块的次数肯定不变）
对于修改而言，由于在块内的强制性修改，最多根号n次，所以总共的也是n根号n的复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int k[2000005];
int to[2000005];//跳出自己块后将会到达的地点
int cnt[2000005];//跳出属于自己块的次数
int sq;
int ingrp(int x){//寻找在哪一个分块中
return ceil(1.0*x/sq);
}
int findid(int x){//寻找在分块中的排位
if(x%sq!=0)
return x%sq;
else
return sq;
}
signed main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
sq=floor(1.0*sqrt(n));
for(int i=1;i<=n;i++){
cin >> k[i];
}
for(int i=n;i>=1;i--){
if(i+k[i]>n){
to[i]=n+1;
cnt[i]=1;
continue;
}
int nxt=i+k[i];
if(ingrp(i)==ingrp(nxt)){//两者在同一块
to[i]=to[nxt];
cnt[i]=cnt[nxt]+1;
}
else{//两者不在同一块
to[i]=nxt;
cnt[i]=1;
}
}
int q;
cin >> q;
while(q--){
int opt;
cin >> opt;
if(opt==1){
int pos;
cin >> pos;
pos++;
int ans=0;
while(pos!=n+1){
ans+=cnt[pos];
pos=to[pos];
}
cout<<ans<<endl;
}
else{
int x,y;
cin >> x >> y;//修改x为y。
x++;
k[x]=y;
int gp=ingrp(x);
int nxt=x+k[x];
if(nxt>n){
to[x]=n+1;
cnt[x]=1;
}
else{
if(gp==ingrp(nxt)){
to[x]=to[nxt];
cnt[x]=cnt[nxt]+1;
}
else{
to[x]=nxt;
cnt[x]=1;
}
}//先把这个位置上的修改了;
for(int i=x-1;i>=1&&ingrp(i)==gp;i--){
if(i+k[i]>n){
to[i]=n+1;
cnt[i]=1;
continue;
}
int nt=i+k[i];
if(ingrp(i)==ingrp(nt)){//两者在同一块
to[i]=to[nt];
cnt[i]=cnt[nt]+1;
}
else{//两者不在同一块
to[i]=nt;
cnt[i]=1;
}
}
}
}
}