洛谷 P3203 [HNOI2010]弹飞绵羊

题意简述

有n个点，第i个点有一个ki，表示到达i这个点后可以到i + ki这个点

支持修改ki和询问一点走几次能走出所有点两个操作

题解思路

分块，

对于每个点，维护它走到下一块所经过的点数，它走到下一块到的店的编号

每次修改只会对这块左端点到这个点产生影响

代码

#include <cmath>

#include <cstdio>

using namespace std;

struct Point{

    int k, s, x, num;

}p[200010];

int n, m, len, ii, ans;

void update(int x)

{

    int xx = x + p[x].k;

    if (xx >= n) p[x].s = 1, p[x].x = -1;

    else if (p[x].num != p[xx].num) p[x].s = 1, p[x].x = xx;

    else p[x].s = p[xx].s + 1, p[x].x = p[xx].x;

}

int main()

{

    scanf("%d", &n);

    len = sqrt(n);

    for (register int i = 0; i < n; ++i)

    {

        scanf("%d", &p[i].k);

        p[i].num = i / len;

    }

    for (register int i = n - 1; i + 1; --i)

        update(i);

    scanf("%d", &m);

    for (register int i = 1; i <= m; ++i)

    {

        int opt;

        scanf("%d", &opt);

        if (opt == 1)

        {

            int cnt = 0;

            scanf("%d", &ii);

            for (ans = 0; ii != -1; ans += p[ii].s, ii = p[ii].x)

                ++cnt;

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

        }

        else

        {

            scanf("%d", &ii);

            scanf("%d", &p[ii].k);

            for (register int j = ii; j >= 0 && p[j].num == p[ii].num; --j)

                update(j);

        }

    }

}

巴特西

洛谷 P3203 [HNOI2010]弹飞绵羊

题意简述

题解思路

代码

最新文章

热门文章