弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MB
Description
某天，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。
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
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()
{
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);
}
}
}
|
