题意

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$。

思路

这是一道经典的 LCT 题，但是并不会 LCT 怎么办呢？那就让它变成一道经典的 分块 题吧。

（别忘了编号集体加 $1$）。

既然是跳跃，那就能联想到，要搞一个类似链表的数组，我们考虑对 $n$ 个装置作分块处理，维护 $t{o}_i$ 表示从装置 $i$ 开始跳，跳出 $i$ 所在块后，跳到了哪里；$st{p}_i$ 表示跳了多少步跳出本块。

那么我们发现几个有意思的结论：

• 如果从 $1$ 开始跳，利用 $to$ 数组，块长次就可以跳完所有装置，也就是说一次查询的时间复杂度是 $\Theta (\sqrt{n})$；
• 如果块内的装置被修改，那么只有对应块内元素的 $to,stp$ 数组需要修改，并不影响别的块。

考虑怎么维护块内的 $to,stp$，其实可以直接扫过去的，期望复杂度 $\Theta (n\sqrt{n})$：

for(int i=/*左端点*/;i<=/*右端点*/;i++)
{
	ll tem=i,cnt=0;
	while(1)
	{
		if(bel[tem]!=bel[i])//跳出本块
		{
			stp[i]=cnt;
			if(tem>n)to[i]=n+1;
			else to[i]=tem;
			break;
		}
		cnt++;
		tem=tem+a[tem];
	}
}

但是写完代码，兴冲冲交上去，TLE 3 个点。我们发现，正着搜其实不优；但是如果我们反着搜，就可以利用刚刚处理好的点：

for(int i=n;i>=1;i--)//倒序枚举，利用后继凹时间 
{
	ll tem=i,cnt=0;
	while(1)
	{
		if(bel[tem]!=bel[i])
		{
			stp[i]=cnt;
			if(tem>n)to[i]=n+1;
			else to[i]=tem;
			break;
		}
		if(stp[tem]||to[tem])
		{
			stp[i]=cnt+stp[tem];
			to[i]=to[tem];
			break;
		}
		cnt++;
		tem=tem+a[tem];
	}
}

时间复杂度 $\Theta (m\sqrt{n})$。

如果想要一个老哥做，作者老矣不能饭否，去学 LCT 吧。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9;
ll n,q,a[N];
ll bSize,cnt_b,bel[N],bl[N],br[N];
ll stp[N],to[N];
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 i=n;i>=1;i--)//倒序枚举，利用后继凹时间 
	{
		ll tem=i,cnt=0;
		while(1)
		{
			if(bel[tem]!=bel[i])
			{
				stp[i]=cnt;
				if(tem>n)to[i]=n+1;
				else to[i]=tem;
				break;
			}
			if(stp[tem]||to[tem])
			{
				stp[i]=cnt+stp[tem];
				to[i]=to[tem];
				break;
			}
			cnt++;
			tem=tem+a[tem];
		}
	}
//	for(int i=1;i<=n;i++)
//	cout<<to[i]<<" "<<stp[i]<<endl;
}
void update(ll x,ll k)
{
	a[x]=k;
	ll t=bel[x];
	for(int i=bl[t];i<=br[t];i++)
	stp[i]=to[i]=0;
	for(int i=br[t];i>=bl[t];i--)
	{
		ll tem=i,cnt=0;
		while(1)
		{
			if(bel[tem]!=bel[i])
			{
				stp[i]=cnt;
				if(tem>n)to[i]=n+1;
				else to[i]=tem;
				break;
			}
			if(stp[tem]||to[tem])
			{
				stp[i]=cnt+stp[tem];
				to[i]=to[tem];
				break;
			}
			cnt++;
			tem=tem+a[tem];
		}
	}
}
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)
		{
			ll tem=x,ret=0;
			while(1)
			{
				if(tem>n)
				{
					printf("%lld\n",ret);
					break;
				}
				ret+=stp[tem];//链表，只和块内的元素相关 
				tem=to[tem];
			}
		}
		else 
		{
			scanf("%lld",&k);
			update(x,k);
		}
	}
    return 0;
}