题意

L 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。

绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，L 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入：

第一行包含一个整数 $n$，表示地上有 $n$ 个装置，装置的编号从 $0\sim n-1$。

接下来一行有 $n$ 个正整数，依次为那 $n$ 个装置的初始弹力系数。

第三行有一个正整数 $m$，表示操作次数。接下来 $m$ 行每行至少有两个数 $i,j$。

• 若 $i=1$，你要输出从编号为 $j$ 的装置出发被弹几次后被弹飞

• 若 $i=2$，则还会再输入一个正整数 $k$，表示编号为 $j$ 的弹力装置的系数被修改成 $k$。

$1\le n\le 2\times 10^5$，$1\le m\le 10^5$。

思路

upd：一年后回来复健 OI 了，复习到分块看到这道题。

太久没有看过题目，我是根据查询时候，发现维护全局的跳跃终点和跳跃次数是 $O(1)$ 的，但是修改牵一发而动全身需要 $O(n)$。遇到这种就要想到用分块均衡：

考虑牺牲查询时候的复杂度，变为 $O(\sqrt{n})$，转为维护块内每个点跳出块的落点 $t{o}_i$ 和次数 $cn{t}_i$。这样修改块内某个值的时候，因为其他块的参数指向后继块，这些参数只与块内的 $k$ 有关，所以修改当前块对其他块没有影响。

void upd(ll x)
{
	ll l=bl[x],r=br[x];
	for(int i=l;i<=r;i++)
	to[i]=cnt[i]=0;
	for(int i=r;i>=l;i--)
	{
		if(i+a[i]>r)to[i]=i+a[i],cnt[i]=1;
		else to[i]=to[i+a[i]],cnt[i]=cnt[i+a[i]]+1;
	}
}
//原则上修改一个点会影响前面所有点的答案，但是如此维护只影响块内该点的前驱
//修改是容易的，块内维护前驱即可
...
ll query(ll x)
{
	ll ret=0;
	while(x<=n)
	{
		ret+=cnt[x];
		x=to[x];//跳跃保持根号复杂度，to与块有关？ 
	}
	return ret;
}
//每个块的to,cnt相对独立

代码

复健一天写的代码奇短无比，不知道以前在干什么……

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9;
ll n,Q;
ll a[N];
ll bSize,cnt_b,bel[N],bl[N],br[N];
ll to[N],cnt[N];
void upd(ll x)
{
	ll l=bl[x],r=br[x];
	for(int i=l;i<=r;i++)
	to[i]=cnt[i]=0;
	for(int i=r;i>=l;i--)
	{
		if(i+a[i]>r)to[i]=i+a[i],cnt[i]=1;
		else to[i]=to[i+a[i]],cnt[i]=cnt[i+a[i]]+1;
	}
}
void init()
{
	bSize=sqrt(n);
	cnt_b=n/bSize;
	if(n%bSize)cnt_b++;
	for(int i=1;i<=n;i++)
	bel[i]=(i-1)/bSize+1;
	for(int i=1;i<=cnt_b;i++)
	{
		bl[i]=(i-1)*bSize+1;
		br[i]=i*bSize;
	}
	br[cnt_b]=n;
	for(int x=1;x<=cnt_b;x++)
	upd(x);
}
void modify(ll x,ll k)//指向块外的，修改只影响块内 
{
	ll bx=bel[x];
	a[x]=k;
	upd(bx);
}
ll query(ll x)
{
	ll ret=0;
	while(x<=n)
	{
		ret+=cnt[x];
		x=to[x];//跳跃保持根号复杂度，to与块有关？ 
	}
	return ret;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	init();
	scanf("%lld",&Q);
	while(Q--)
	{
		ll op,x,k;
		scanf("%lld%lld",&op,&x);
		x++;
		if(op==1)printf("%lld\n",query(x));
		else 
		{
			scanf("%lld",&k);
			modify(x,k);
		}
	}
	return 0;
}