国际网站开发客户,php网站开发数据列表排重,备案 网站名称什么用,广告设计专业简历题目
题目链接
题意
据说这道题要用一道叫做LCT的数据结构#xff0c;然而我不会。。。
一排有n个弹簧装置#xff0c;从第ii个可一往后跳k[i] role=presentation style=position: relative;k[i]k[i]步。
修改#xff1a;修改某个位…题目
题目链接
题意
据说这道题要用一道叫做LCT的数据结构然而我不会。。。
一排有n个弹簧装置从第iii个可一往后跳k[i]" role="presentation" style="position: relative;">k[i]k[i]k[i]步。
修改修改某个位置弹簧的弹性。查询询问从某个位置出发弹多少次就弹飞了。
题解
分块首先都要先从暴力开始想起 我们记录从任意一个点出发下一次能跳到哪里这样的话我们每次询问只需要一只沿着这条链往下走即可显然最坏的时间复杂度是O(n2)O(n2)O(n^2)修改的时间复杂度为O(1)O(1)O(1)。
优化 让我们使用分块来进行优化我们把一条直线上的n个弹簧进行分块并对于每个弹簧记录两个属性sum[i]sum[i]sum[i]和nxtb[i]nxtb[i]nxtb[i]。
其中sum[i]sum[i]sum[i]表示的含义是从iii弹簧出发在本块内的经过的节点的个数，nxtb[i]" role="presentation" style="position: relative;">nxtb[i]nxtb[i]nxtb[i]表示的是从iiscript typemath/tex idMathJax-Element-479i/script弹簧出发弹到下一块中的第一个弹簧的编号弹飞设置为-1。
这样的话询问的时候我们只需要下面一段代码就可以了。
int now x;
while(x ! -1){ans sum[now];now nxtb[now];
}
预处理的话我们要倒着往前计算因为前面的sum用到了后面的sum。 预处理和修改的话详情请见代码。
代码
#include iostream
#include cstdio
#include algorithm
#include cmath
using namespace std;
const int maxn 200007;
#define pr(x) cout#x:xendl
int Base 450;
int nxtb[maxn];
int val[maxn];
int sum[maxn];
int n,m,op,x,y;
inline void read(int x){scanf( %d,x);
}
int main(){read(n);Base (int) sqrt(n0.5);for(int i 1;i n;i){read(val[i]);}for(int i n;i 1;--i){int j val[i] i;int bl i / Base;int br j / Base;if(j n){nxtb[i] -1;sum[i] 1;}else if(br bl){//属于同一个块nxtb[i] nxtb[j];sum[i] sum[j]1;}else{//不属于同一个块nxtb[i] j;sum[i] 1;}}read(m);while(m--){read(op);if(op 1){//询问read(x);x;int ans 0;int now x;while(now ! -1){ans sum[now];now nxtb[now];}printf(%d\n,ans);}else{//修改read(x);read(y);x;val[x] y;int j x y;int bl x / Base;int br j / Base;if(j n){sum[x] 1;nxtb[x] -1;}else if(bl br){//属于用一个块sum[x] sum[j] 1;nxtb[x] nxtb[j];}else{//不属于同一个块sum[x] 1;nxtb[x] j;}for(int i x-1;i max(1,bl*Base);--i){//更新与x属于同一块的可能被x影响的弹簧。j i val[i];br j / Base;if(br bl){sum[i] sum[j] 1;nxtb[i] nxtb[j];}}}}return 0;
}
