BZOJ2002 - [Hnoi2010]Bounce 弹飞绵羊

2017/02/22

题目

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

样例输入:

4
1 2 1 1
3
1 1
2 1 1
1 1

样例输出:

2
3

解法

按位置分块,每个点记录跳出分块的步数以及跳到下一分块的哪个点。

hzwer

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 200200;
int N, M;
int block, cnt;
int A[MAX_N], L[MAX_N], R[MAX_N], st[MAX_N], pt[MAX_N], belong[MAX_N];

int main() {
    scanf("%d", &N); block = int(sqrt(N));

    for(int i=1;i<=N;i++) {
        scanf("%d", &A[i]);
    }

    if(N % block) cnt = N / block + 1;

    for(int i=1;i<=cnt;i++)
        L[i] = (i - 1) * block + 1, R[i] = i * block;
    R[cnt] = N;

    for(int i=1;i<=N;i++)
        belong[i] = (i-1) / block + 1;

    for(int i=N;i>0;i--) {
        if(i + A[i] > N) st[i] = 1;
        else if(belong[i] == belong[i + A[i]])
            st[i] = st[i + A[i]] + 1, pt[i] = pt[i + A[i]];
        else st[i] = 1, pt[i] = i + A[i];
    }

    scanf("%d", &M);

    int op, a, b;
    for(int i=1;i<=M;i++) {
        scanf("%d", &op);
        switch(op) {
        case 1: {
            scanf("%d", &a); a++;
            int t = 0;
            while(true) {
                t += st[a];
                if(!pt[a]) break;
                a = pt[a];
            }
            printf("%d\n", t);
        } break;
        case 2: {
            scanf("%d %d", &a, &b); a++;
            A[a] = b;
            for(int i=a;i>=L[belong[a]];i--) {
                if(belong[i] == belong[i + A[i]])
                    st[i] = st[i + A[i]] + 1, pt[i] = pt[i + A[i]];
                else st[i] = 1, pt[i] = i + A[i];
            }
        } break;
        }
    }
}