【题目来源】https://www.acwing.com/problem/content/2168/https://www.luogu.com.cn/problem/P3203【题目描述】某天Lostmonkey 发明了一种超级弹力装置为了在他的绵羊朋友面前显摆他邀请小绵羊一起玩个游戏。游戏一开始Lostmonkey 在地上沿着一条直线摆上 n 个装置每个装置设定初始弹力系数 ki当绵羊达到第 i 个装置时它会往后弹 ki 步达到第 iki 个装置若不存在第 iki 个装置则绵羊被弹飞。绵羊想知道当它从第 i 个装置起步时被弹几次后会被弹飞。为了使得游戏更有趣Lostmonkey 可以修改某个弹力装置的弹力系数任何时候弹力系数均为正整数。【输入格式】第一行包含一个整数 n表示地上有 n 个装置装置的编号从 0∼n−1。接下来一行有 n 个正整数依次为那 n 个装置的初始弹力系数。第三行有一个正整数 m表示操作次数。接下来 m 行每行至少有两个数 i,j。1若 i1你要输出从编号为 j 的装置出发被弹几次后被弹飞2若 i2则还会再输入一个正整数 k表示编号为 j 的弹力装置的系数被修改成 k。【输出格式】对于每个 i1 的操作输出一行一个整数表示答案。【输入样例】41 2 1 131 12 1 11 1【输出样例】23【算法分析】● 题目同时存在大量查询与大量修改纯暴力算法必然超时。下面代码提交洛谷测评时4 个 AC6 个 TLE超时。#include bits/stdc.h using namespace std; const int N2e55; int a[N]; int n,m; int query(int start) { int steps0; int curstart; while(curn) { curcura[cur]; steps; } return steps; } int main() { ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i0; in; i) cina[i]; cinm; while(m--) { int op,x; cinopx; if(op1) coutquery(x)\n; else { int k; cink; a[x]k; } } return 0; } /* in: 4 1 2 1 1 3 1 1 2 1 1 1 1 out: 2 3 */● 本题其实就是动态树 LCT的模板题这里用来练习分块。● 分块算法区间更新、区间查询代码实例详见https://blog.csdn.net/hnjzsyjyj/article/details/138863063本例介绍各数组下标从 0 开始的分块算法单点更新、单点查询代码。● 分块是用线段树的分区思想改良的暴力法。代码比线段树简单。效率比普通暴力法高。分块适合求解 mn10^5规模的问题。或m*sqrt(n)≈10^7的问题。其中n 为元素个数m 为操作次数。● 分块操作的基本要素1块的大小用 block 表示。通常令blocksqrt(n)。其中n 为元素个数。2块的数量用 cnt 表示。计算块的数量的代码如下int blocksqrt(n); int cntn/block; if(n % block) cnt;3块的左边界 le[] 及右边界 ri[]。若用 le[i] 和 ri[i] 分别表示块 i 的第一个和最后一个元素的位置。若下标从 1 开始则有le[1]1, ri[1]block; le[2]block1, ri[2]2*block; …… le[i](i-1)*block1, 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](i1)*block-1; ……4定义 pos[i] 为第 i 个元素所在的块。若下标从 1 开始则有pos[i](i-1)/block1。其中blocksqrt(n)。若下标从 0 开始则有pos[i]i/block。其中blocksqrt(n)。●update函数的作用当某个位置的弹力系数被修改后重新计算它所在块内所有受影响位置的跳转信息。step[i]从 i 开始直到第一次跳出 i 所在的块一共需要多少步to[i]执行完 step[i] 步后到达的位置可能在另一个块内也可能超出 n 表示被弹飞。pos[i]位置 i 所属的块编号。le[i] / ri[i]第 i 个块的左边界/右边界。【算法代码】#include bits/stdc.h using namespace std; const int maxn1e65; int a[maxn],le[maxn],ri[maxn]; int pos[maxn]; int to[maxn],step[maxn]; int n,m; void build(int n) { int blocksqrt(n); int cntn/block; if(n%block) cnt; for(int i0; icnt; i) { le[i]i*block; ri[i](i1)*block-1; } ri[cnt-1]n-1; for(int i0; in; i) pos[i]i/block; } void update(int L, int R) { for(int iR; iL; i--) { if(ia[i]ri[pos[i]]) { to[i]ia[i]; step[i]1; } else { to[i]to[ia[i]]; step[i]step[ia[i]]1; } } } int query(int x) { int ans0; while(xn) { ansstep[x]; xto[x]; } return ans; } int main() { cinn; for(int i0; in; i) cina[i]; build(n), update(0,n-1); cinm; while(m--) { int op,x,y; cinopx; if(op1) coutquery(x)endl; else { ciny; 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 1 out: 2 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/138863063https://www.acwing.com/solution/content/92055/https://www.acwing.com/solution/content/170541/https://www.luogu.com.cn/problem/solution/P3203https://www.cnblogs.com/xuyixuan/p/9462001.html