洛谷 P3203：弹飞绵羊 ← 分块算法（单点更新、单点查询）

【题目来源】
https://www.acwing.com/problem/content/2168/
https://www.luogu.com.cn/problem/P3203

【题目描述】
某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。
游戏一开始，Lostmonkey 在地上沿着一条直线摆上 n 个装置，每个装置设定初始弹力系数 ki，当绵羊达到第 i 个装置时，它会往后弹 ki 步，达到第 i+ki 个装置，若不存在第 i+ki 个装置，则绵羊被弹飞。
绵羊想知道当它从第 i 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

【输入格式】
第一行包含一个整数 n，表示地上有 n 个装置，装置的编号从 0∼n−1。
接下来一行有 n 个正整数，依次为那 n 个装置的初始弹力系数。
第三行有一个正整数 m，表示操作次数。接下来 m 行每行至少有两个数 i,j。
（1）若 i=1，你要输出从编号为 j 的装置出发被弹几次后被弹飞
（2）若 i=2，则还会再输入一个正整数 k，表示编号为 j 的弹力装置的系数被修改成 k。

【输出格式】
对于每个 i=1 的操作，输出一行一个整数表示答案。

【输入样例】
4
1 2 1 1
3
1 1
2 1 1
1 1

【输出样例】
2
3

【算法分析】
● 本题其实就是动态树 LCT 的模板题，这里用来练习分块。

● 分块算法（区间更新、区间查询）代码实例详见：https://blog.csdn.net/hnjzsyjyj/article/details/138863063
本例介绍各数组下标从 0 开始的分块算法（单点更新、单点查询）代码。

● 分块是用线段树的分区思想改良的暴力法。代码比线段树简单。效率比普通暴力法高。分块适合求解 m=n=10^5 规模的问题。或 m*sqrt(n)≈10^7 的问题。其中，n 为元素个数，m 为操作次数。

● 分块操作的基本要素
（1）块的大小用 block 表示。通常，令 block=sqrt(n)。其中，n 为元素个数。
（2）块的数量用 cnt 表示。计算块的数量的代码如下：

int block=sqrt(n);
int cnt=n/block;
if(n % block) cnt++;

（3）块的左边界 le[] 及右边界 ri[]。
若用 le[i] 和 ri[i] 分别表示块 i 的第一个和最后一个元素的位置。
若下标从 1 开始，则有：

le[1]=1, ri[1]=block;
le[2]=block+1, ri[2]=2*block;
……
le[i]=(i-1)*block+1, ri[i]=i*block;
……

若下标从 0 开始，则有：

le[0]=0, ri[0]=block-1;
le[1]=block, ri[1]=2*block-1;
……
le[i]=i*block, ri[i]=(i+1)*block-1;
……

（4）定义 pos[i] 为第 i 个元素所在的块。
若下标从 1 开始，则有 pos[i]=(i-1)/block+1。其中，block=sqrt(n)。
若下标从 0 开始，则有 pos[i]=i/block。其中，block=sqrt(n)。

● 数组 step[x]，表示从 x 跳出当前块所用步数；数组 to[x]，表示从 x 跳出当前块到达的位置。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;
int a[maxn],le[maxn],ri[maxn];
int pos[maxn];
int to[maxn],step[maxn];
int n,m;void build(int n) {int block=sqrt(n);int cnt=n/block;if(n%block) cnt++;for(int i=0; i<cnt; i++) {le[i]=i*block;ri[i]=(i+1)*block-1;}ri[cnt-1]=n-1;for(int i=0; i<n; i++) pos[i]=i/block;
}void update(int L, int R) {for(int i=R; i>=L; i--) {if(i+a[i]>ri[pos[i]]) {to[i]=i+a[i];step[i]=1;} else {to[i]=to[i+a[i]];step[i]=step[i+a[i]]+1;}}
}int query(int x) {int ans=0;while(x<n) {ans+=step[x];x=to[x];}return ans;
}int main() {cin>>n;for(int i=0; i<n; i++) cin>>a[i];build(n), update(0,n-1);cin>>m;while(m--) {int op,x,y;cin>>op>>x;if(op==1) cout<<query(x)<<endl;else {cin>>y;a[x]=y;update(le[pos[x]],ri[pos[x]]);}}return 0;
}/*
in:
4
1 2 1 1
3
1 1
2 1 1
1 1out:
2
3
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/138863063
https://www.acwing.com/solution/content/92055/
https://www.acwing.com/solution/content/170541/
https://www.luogu.com.cn/problem/solution/P3203
https://www.cnblogs.com/xuyixuan/p/9462001.html