BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊
程序员文章站
2022-04-16 10:14:00
2002: [Hnoi2010]Bounce 弹飞绵羊 Description 某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时 ......
2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 13360 Solved: 6782
[Submit][Status][Discuss]
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<=10000,对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况,你都要输出一个需要的步数,占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
3
HINT
Source
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 const int maxn=200000+5; 6 7 int block,belong[maxn],a[maxn],n,m,num; 8 int l[maxn],r[maxn],cnt[maxn],end[maxn]; 9 10 inline void bt() 11 { 12 block=sqrt(n); 13 num=n/block; 14 if(n%block) 15 num++; 16 for(int i=1;i<=num;++i) 17 l[i]=(i-1)*block+1,r[i]=i*block; 18 r[num]=n; 19 for(int i=1;i<=n;i++) 20 belong[i]=(i-1)/block+1; 21 22 for(int i=n;i>0;i--) 23 { 24 if(i+a[i]>n) 25 cnt[i]=1,end[i]=-1; 26 else if(belong[i]==belong[i+a[i]]) 27 cnt[i]=cnt[i+a[i]]+1,end[i]=end[i+a[i]]; 28 else 29 cnt[i]=1,end[i]=i+a[i]; 30 } 31 } 32 33 inline int work(int x) 34 { 35 int ans=0; 36 while(true) 37 { 38 ans+=cnt[x]; 39 if(end[x]<0) 40 break; 41 x=end[x]; 42 } 43 return ans; 44 } 45 46 inline void update(int x,int y) 47 { 48 a[x]=y; 49 for(int i=x;i>=l[belong[x]];i--) 50 { 51 if(i+a[i]>n) 52 cnt[i]=1,end[i]=-1; 53 else if(belong[i]==belong[i+a[i]]) 54 cnt[i]=cnt[i+a[i]]+1,end[i]=end[i+a[i]]; 55 else 56 cnt[i]=1,end[i]=i+a[i]; 57 } 58 return ; 59 } 60 61 int main() 62 { 63 scanf("%d",&n); 64 for(int i=1;i<=n;i++) 65 scanf("%d",&a[i]); 66 bt(); 67 scanf("%d",&m); 68 for(int i=1;i<=m;i++) 69 { 70 int x; 71 scanf("%d",&x); 72 if(x==1) 73 { 74 int y; 75 scanf("%d",&y); 76 y++; 77 printf("%d\n",work(y)); 78 } 79 else 80 { 81 int y,z; 82 scanf("%d%d",&y,&z); 83 y++; 84 update(y,z); 85 } 86 } 87 return 0; 88 }
上一篇: 如何选择合适的PHP版本
下一篇: python高级——目录