第一次学习分块,似乎有点小激动
这是黄学长的分块入门博客「分块」数列分块入门1 – 9 by hzwer
题目描述
某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。
输入输出格式
输入格式:
第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1。
接下来一行有n个正整数,依次为那n个装置的初始弹力系数。
第三行有一个正整数m,
接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。
输出格式:
对于每个i=1的情况,你都要输出一个需要的步数,占一行。
说明
对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000
不看数据范围的话,题目还是挺友好的对不对...用f[i]表示在第i个装置上出发几次后被弹飞,毕竟对于任意i的f[i]是唯一的。
然而,然而题目要求在线更新并询问……
那第一感觉就是路径压缩,每一次更改ki之后向后修改f[i]并修改f[i + k[i]]。但实际上这样会有大量的冗余操作,有可能它之后跳的位置都没有被修改过。
那么在f[i]上挂链记录跳到i的位置吗?每次修改ki向前更新?
然而这样又是O(n)的更新复杂度……要是遇上1 1 1 1 1...的无良数据呢……
所以就有了“分块”这种奇妙的操作……呃其实我觉得分块就是一种有效优化的暴力嘛(但是似乎这样看来有些其他算法也是暴力嘛(是亦彼也,彼亦是也))
我们把n分成m块,一般情况下m=sqrt(n)(不过具体题目具体分析,通常m的大小有三种方式确定:1.m=sqrt(n) 2.用大数据观察,手调m 3.分析并使用均值不等式)
由于块大小是远远小于总数的,我们每一次更新只要在块内,时间复杂度就是足够的。至于后续的处理,分块也能够起到优化作用。例如本题,用nxt[i]记录i在跳出当前块后跳到的位置,w[i]记录i跳出当前块的步数,不仅在查询时可省去大量的块内跳跃的模拟,在更新时候逆序处理也就能够利用已处理的w[],nxt[],进一步奇妙优化。(是的没有错,我因为暴力更新块内元素,即便开O2并且把m=sqrt(n)*2/7了仍然最后一点TLE)
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std; int k[],w[],nxt[],m,n;
int bl[],blo; inline int dist(int x)
{
if (x >= n)return ;
return dist(nxt[x]) + w[x];
}
inline int away(int x)
{
int r,cnt = ,t = x;
if ((bl[x])*blo - > n-)r = n-;
else r = (bl[x])*blo - ;
cnt++;x+=k[x];
if (x <= r){
cnt += w[x];
x = nxt[x];
}
nxt[t] = x;
return cnt;
} int main()
{
scanf("%d",&n);
blo = sqrt(n);
if (blo > )blo = (blo*)/;
for (int i=; i<n; i++)
{
scanf("%d",&k[i]);
bl[i] = i/blo + ;
}
memset(w, , sizeof(w));
for (int i=n-; i>=; i--) w[i] = away(i);
scanf("%d",&m);
for (int i=; i<=m; i++)
{
int fl, x, y;
scanf("%d%d",&fl,&x);
if (!(fl-))printf("%d\n",dist(x));
else{
scanf("%d",&y);
k[x] = y;
for (int j=x; j>=(bl[x]-)*blo; j--)w[j] = away(j);
}
}
return ;
}
对了还有一个坑点,本题元素下标自0开始