首页 > 代码库 > [BZOJ2002][Hnoi2010]Bounce 弹飞绵羊
[BZOJ2002][Hnoi2010]Bounce 弹飞绵羊
2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 10814 Solved: 5562
[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
一看到此题就想到了递推+分块,写完后莫名WA了2次后来才发现修改时能将绵羊弹飞的节点的to数组没归0.
后来看题解发现正解是动态树(LCT)蒟蒻的我并不会写,这里贴出分块代码
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int read() 9 { 10 char ch=getchar();int x=0,f=1; 11 while(!isdigit(ch)){if(ch==‘-‘)f=-1; ch=getchar();} 12 while(isdigit(ch)){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 int n; 16 int a[200002]; 17 int belong[200002],to[200002],b[200002]; 18 int size; 19 int main() 20 { 21 n=read(); 22 size=sqrt(n); 23 for(int i=1;i<=n;i++) 24 { 25 a[i]=read(); 26 belong[i]=(i-1)/size+1; 27 } 28 for(int i=n;i>=1;i--) 29 { 30 if(i+a[i]>n) b[i]=1; 31 else if(belong[i]==belong[i+a[i]]){b[i]=b[i+a[i]]+1;to[i]=to[i+a[i]];} 32 else{b[i]=1;to[i]=i+a[i];} 33 } 34 int m=read(); 35 while(m--) 36 { 37 int ask=read(); 38 if(ask==1) 39 { 40 int now=read(); 41 now++; 42 int ans=0; 43 while(now) 44 { 45 ans+=b[now]; 46 now=to[now]; 47 } 48 printf("%d\n",ans); 49 } 50 else 51 { 52 int now=read(),c=read(); 53 now++; 54 a[now]=c; 55 int bn=belong[now]; 56 for(int i=now;belong[i]==bn;i--) 57 { 58 if(i+a[i]>n) b[i]=1,to[i]=0; 59 else if(belong[i]==belong[i+a[i]]){b[i]=b[i+a[i]]+1;to[i]=to[i+a[i]];} 60 else{b[i]=1;to[i]=i+a[i];} 61 } 62 } 63 } 64 }
[BZOJ2002][Hnoi2010]Bounce 弹飞绵羊
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。