电脑做网站空间,网站哪个公司做的,wordpress qa,龙岩做网站开发价格【题目来源】https://www.acwing.com/problem/content/2168/https://www.luogu.com.cn/problem/P3203【题目描述】 某天#xff0c;Lostmonkey 发明了一种超级弹力装置#xff0c;为了在他的绵羊朋友面前显摆#xff0c;他邀请小绵羊一起玩个游戏。 游戏一开始#xff0c;L…【题目来源】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 的操作输出一行一个整数表示答案。【输入样例】 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 开始的分块算法单点更新、单点查询代码。 ● 分块是用线段树的分区思想改良的暴力法。代码比线段树简单。效率比普通暴力法高。分块适合求解 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)。 ● 数组 step[x]表示从 x 跳出当前块所用步数数组 to[x]表示从 x 跳出当前块到达的位置。【算法代码】
#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 1out:
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
