【分块】[HNOI2010]弹飞绵羊&分块大法祭

分块（似乎还有一种动态树（LCT）做法）

第一次学习分块，似乎有点小激动

题目描述

某天，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开始

巴特西

【分块】[HNOI2010]弹飞绵羊&分块大法祭

题目描述

输入输出格式

说明

最新文章

热门文章