P3203做题记录

一种更简单的想法，只用用分块思想（或者根号分治？）不用分块。

先考虑暴力怎么做：修改直接改，查询不停跳下一个点。但这样会被卡到 \(O(n^2)\)。

考虑分块思想优化：如果保证每次至少跳 \(\sqrt n\) 的距离，总复杂度就会降到 \(O(n\sqrt n)\)。

于是可以维护每个点开始至少跳 \(\sqrt n\) 的距离要跳多少次，会跳多远。

但是发现这样修改的时候，在它前面的所有点都会被影响，复杂度炸了。所以换作维护从一个点开始到点 \(x\)，使得从这里再跳一次就至少跳了 \(\sqrt n\) 的距离。这样就只用重构被修改的点之前的 \(\sqrt n\) 个点了。

总复杂度 \(O(n\sqrt n)\)。

只放核心代码。

code：

inline void pushup(int x){
	c[x]=1;
	f[x]=e[x];
	while(x+f[x]<=n&&f[x]+f[x+f[x]]<len){
		c[x]+=c[x+f[x]];
		f[x]+=f[x+f[x]];
	}
}
int query(int x){
	int ret=0;
	while(x<=n){
		ret+=c[x];
		x+=f[x];
	}
	return ret;
}
void update(int x,int y){
	e[x]=y;
	pushup(x);
	for(int i=x-1;i>=max(1,x-len);i--){
		pushup(i);
	}
}

温馨提醒：重构和初始化一定要从后往前。