弹飞绵羊[HNOI2010]

——BZOJ2002

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数\(n\)，表示地上有\(n\)个装置，装置的编号从\(0\)到\(n-1\),接下来一行有\(n\)个正整数，依次为那\(n\)个装置的初始弹力系数。第三行有一个正整数\(m\)，接下来\(m\)行每行至少有两个数\(i\)、\(j\)，若\(i=1\)，你要输出从\(j\)出发被弹几次后被弹飞，若\(i=2\)则还会再输入一个正整数\(k\)，表示第j个弹力装置的系数被修改成\(k\)。对于\(20\%\)的数据\(n,m \le 10000\)，对于\(100\%\)的数据\(n \le 200000\),\(m \le 100000\)

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

Sample Output

2

3

Analysis

这道题的正解是LCT?

不过这是省选题，一定有其他的解法，这里就有一个分块做法。

O(n)维护两个数组to和outto,to代表每个位置跳到块内最后一个位置的最少步数，outto表示这个位置跳到第二个块的新位置。这两个数组倒着维护。

然后就能做了。

询问和修改的时间复杂度都是\(O(\sqrt n)\)，因为一共\(\sqrt n\)个块,每个块内\(\sqrt n\)个元素。

code

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int ans = 0,op = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9')

    {

    if(ch == '-') op = -1;

    ch = getchar();

    }

    while(ch >= '0' && ch <= '9')

    {

    ans *= 10;

    ans += ch - '0';

    ch = getchar();

    }

    return ans * op;

}

const int maxn = 2e5 + 5;

int seq[maxn];

int blo[10005];

int to[maxn];

int outto[maxn];

int m,n;

int cnt,num,cntt=1;

int qpos(int x)

{

    return x % cnt == 0 ? x / cnt : x / cnt + 1;

}

int qlast(int x)

{

    if(qpos(x) == num)

        return n;

    return cnt * qpos(x);

}

int qfirst(int x)

{

    return cnt * (qpos(x) - 1) + 1;

}

int main()

{

    n = read();

    cnt = sqrt(n);

    num = qpos(n);

    for(int i=1;i<=n;i++)

        seq[i] = read();

    for(int i=n;i>=1;i--)

    {

        if(i + seq[i] > qlast(i))

        {

            to[i] = i + seq[i];

            outto[i] = 1;

        }

        else

        {

            to[i] = to[i+seq[i]];

            outto[i] = outto[i+seq[i]] + 1;

        }

    }

//	printf("\n***\n");

//	for(int i=1;i<=n;i++)

//		printf("%d ",to[i]);

//	printf("\n");

//	for(int i=1;i<=n;i++)

//		printf("%d ",outto[i]);

//	printf("\n***\n");

    m = read();

    for(int ct=1;ct<=m;ct++)

    {

        int ju;

        ju = read();

        if(ju == 1)

        {

            int x,ans;

            x = read();

            x+=1;

            ans = outto[x];

            x = to[x];

            while(x <= n)

            {

                ans += outto[x];

                x = to[x];

            }

            printf("%d\n",ans);

        }

        else

        {

            int x,k;

            x = read();

            k = read();

            x+=1;

            seq[x] = k;

            for(int i=x;i>=qfirst(x);i--)

            {

                if(i + seq[i] > qlast(i))

                {

                    to[i] = i + seq[i];

                    outto[i] = 1;

                }

                else

                {

                    to[i] = to[i+seq[i]];

                    outto[i] = outto[i+seq[i]] + 1;

                }

            }

        }

    }

    return 0;

}

秒客网