首页 > 代码库 > BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊
BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊
2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 3952 Solved: 2101
[Submit][Status]
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
Splay 启发式合并
题解：
原来分块水过。
把上一题的程序加个pushup就能A。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 200000+1000 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 using namespace std; 19 inline int read() 20 { 21 int x=0,f=1;char ch=getchar(); 22 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 23 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 24 return x*f; 25 } 26 int fa[maxn],c[maxn][2],sta[maxn],next[maxn],n,m,s[maxn]; 27 bool rev[maxn]; 28 inline bool isroot(int x) 29 { 30 return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; 31 } 32 inline void pushup(int x) 33 { 34 s[x]=s[c[x][0]]+s[c[x][1]]+1; 35 } 36 void rotate(int x) 37 { 38 int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1; 39 if(!isroot(y))c[z][c[z][1]==y]=x; 40 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 41 c[y][l]=c[x][r];c[x][r]=y; 42 pushup(y);pushup(x); 43 } 44 void pushdown(int x) 45 { 46 if(!rev[x])return; 47 rev[x]^=1;rev[c[x][0]]^=1;rev[c[x][1]]^=1; 48 swap(c[x][0],c[x][1]); 49 } 50 void splay(int x) 51 { 52 int top=0;sta[++top]=x; 53 for(int y=x;!isroot(y);y=fa[y])sta[++top]=fa[y]; 54 for(;top;)pushdown(sta[top--]); 55 while(!isroot(x)) 56 { 57 int y=fa[x],z=fa[y]; 58 if(!isroot(y)) 59 { 60 if(c[z][0]==y^c[y][0]==x)rotate(x);else rotate(y); 61 } 62 rotate(x); 63 } 64 65 } 66 void access(int x) 67 { 68 for(int y=0;x;x=fa[x]) 69 { 70 splay(x);c[x][1]=y;y=x; 71 } 72 } 73 void makeroot(int x) 74 { 75 access(x);splay(x);rev[x]^=1; 76 } 77 int find(int x) 78 { 79 access(x);splay(x); 80 while(c[x][0])x=c[x][0]; 81 return x; 82 } 83 void link(int x,int y) 84 { 85 makeroot(x);fa[x]=y;splay(x); 86 } 87 void cut(int x,int y) 88 { 89 makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0; 90 } 91 int main() 92 { 93 freopen("input.txt","r",stdin); 94 freopen("output.txt","w",stdout); 95 n=read(); 96 int ch,x,y,t; 97 for(int i=1;i<=n;i++) 98 { 99 x=read();100 s[i]=1;next[i]=min(n+1,i+x);101 fa[i]=next[i];102 }103 s[n+1]=1;104 m=read();105 while(m--)106 {107 ch=read();108 if(ch==2)109 {110 x=read()+1;y=read();111 t=min(n+1,x+y);112 cut(x,next[x]);link(x,t);next[x]=t;113 }114 else115 {116 x=read()+1;117 makeroot(n+1);access(x);splay(x);printf("%d\n",s[c[x][0]]);118 }119 }120 return 0;121 }
BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。