一种更简单的想法,只用用分块思想(或者根号分治?)不用分块。
先考虑暴力怎么做:修改直接改,查询不停跳下一个点。但这样会被卡到 \(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);
}
}
温馨提醒:重构和初始化一定要从后往前。
标签:分块,复杂度,记录,sqrt,做题,P3203,pushup From: https://www.cnblogs.com/yinhee/p/P3203.html