弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB

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。

Output

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

Sample Input

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

Sample Output

2
　3

HINT

对于20%的数据：n,m<=10000;

对于100%的数据：n<=200000,m<=100000.

Main idea

给定一个位置，走一步可以走到一个指定位置，求走到n以外需要几步，走到的指定位置需要支持修改。

Solution

考虑暴力显然不可做，运用分块，维护两个信息：1.走出当前分块需要几步；2.走出当前分块后到了哪个点。

每次修改更新改点信息以及该块内的点，又因为一个点不一定只影响到该块内直接跳到这个点的点，也有间接关系的可能性存在，直接倒着搜一遍每次在可以跳到的点+1即可。

Code

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;

const int ONE=400001;

int n,Q,P;
int T,x,y;
int num,to;
int a[ONE],To[ONE],F[ONE];
int go,jishu;
int PD[ONE];
int l[ONE],r[ONE];

struct power
{
    int step;
    int to;
    int from;
}C[ONE];

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Query(int x)
{
    int j=x;
    int Ans=0;
    while(j<=n)
    {
        Ans+=C[j].step;
        j=C[j].to;
    }
    return Ans;
}

int Update(int x,int y)
{
    int j=x;
    To[x]=x+y;
    if(To[x]>n) To[x]=n+1;

    jishu=0;
    while(C[j].from==C[x].from)
    {
        j=To[j];
        jishu++;
    }
    C[x].step=jishu; C[x].to=j;

    for(int i=x-1;i>=l[C[x].from];i--)
    {
        int y=To[i];
        if(C[i].from==C[y].from)
        {
            C[i].to=C[y].to;
            C[i].step=C[y].step+1;
        }
    }

}

int main()
{
    // freopen("input.in","r",stdin);
    // freopen("input.out","w",stdout);
    n=get();
    Q=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=get(); To[i]=i+a[i];

        if(To[i]>n) To[i]=n+1;
        if(!((i-1)%Q))
        {
            num++;
            l[num]=i;
        }
        C[i].from=num; r[num]=i;
    }

    for(int i=1;i<=n;i++)
    {
        int j=i;
        jishu=0;
        while(C[j].from==C[i].from)
        {
            j=To[j];
            jishu++;
        }
        C[i].step=jishu;
        C[i].to=j;
        if(C[i].to>n) C[i].to=n+1;
    }

    T=get();
    while(T--)
    {
        P=get();
        if(P==1)
        {
            x=get(); x++;
            printf("%d\n",Query(x));
        }

        if(P==2)
        {
            x=get(); x++;
            y=get();
            Update(x,y);
        }

    }
}