首页 > 代码库 > BZOJ 4764: 弹飞大爷
BZOJ 4764: 弹飞大爷
4764: 弹飞大爷
Time Limit: 30 Sec Memory Limit: 256 MBSubmit: 39 Solved: 24
[Submit][Status][Discuss]
Description
自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们
决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了
第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也
就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替
换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会
把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察
，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位
置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。
Input
第一行为两个整数N和M，代表序列长度和操作次数。
第二行为N个整数，代表初始的小伙伴序列。
接下来有M行，每行代表一个操作。
如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹
起会摔在地上。如果永远不会摔在地上，请输出-1。
如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。
N,M <= 200000 |Ai| < N
Output
对于每次询问操作，输出弹起次数或-1。
Sample Input
3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
Sample Output
3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2
HINT
Source
By YouSiki & GuoZZ
分析：
这是基环森林，如果一个联通块没有换那么就是普通的LCT，如果有环那么大爷就永远不需要落地输出-1...
现在我们断掉环上的任意一条边(x,y)，然后把这条边变成虚边，x就作为这个联通块的根节点，那么x的环父亲就是y，然后删边的时候判断删掉之后xy是否联通，不联通就把xy这条虚边连上...
代码：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=200000+5;int n,m,p[maxn];struct M{ int dis; bool reverse; M *cf,*son[2],*father; inline M(void){ dis=1; cf=NULL; father=NULL; reverse=false; son[1]=son[0]=NULL; } inline void update(void){ dis=1; if(son[0]) dis+=son[0]->dis; if(son[1]) dis+=son[1]->dis; } inline bool isroot(void){ if(father==NULL) return true; if(father->son[0]==this) return false; if(father->son[1]==this) return false; return true; } inline void pushdown(void){ if(reverse){ reverse=false; swap(son[0],son[1]); if(son[0]) son[0]->reverse^=true; if(son[1]) son[1]->reverse^=true; } } }tr[maxn];inline void connect(M *f,M *t,int s){ if(t!=NULL) t->father=f; if(f!=NULL) f->son[s]=t;}inline void rotate(M *t){ M *f=t->father; M *g=f->father; int s=(f->son[1]==t); connect(f,t->son[!s],s); connect(t,f,!s); t->father=g; if(g&&g->son[0]==f) g->son[0]=t; if(g&&g->son[1]==f) g->son[1]=t; f->update();t->update();}inline void push(M *t){ static M *stk[maxn]; int top=0; stk[top++]=t; while(!t->isroot()) stk[top++]=t=t->father; while(top) stk[--top]->pushdown();}inline void splay(M *t){ push(t); while(!t->isroot()){ M *f=t->father; M *g=f->father; if(f->isroot()) rotate(t); else{ bool a=(f&&f->son[1]==t); bool b=(g&&g->son[1]==f); if(a==b) rotate(f),rotate(t); else rotate(t),rotate(t); } }}inline void access(M *t){ M *p=NULL; while(t!=NULL){ splay(t); t->son[1]=p,t->update(); p=t,t=t->father; }}inline void makeroot(M *t){ access(t);splay(t);t->reverse^=true;}inline void cut(M *t){ access(t);splay(t); if(t->son[0]) t->son[0]->father=NULL; if(t->son[1]) t->son[1]->father=NULL; t->son[0]=t->son[1]=NULL;t->update();}inline void link(M *f,M *t){ makeroot(t);t->father=f;}inline M *find(M *t){ access(t); splay(t); M *r=t; while(r->son[0]) r=r->son[0]; return r;}inline void add(M *t,M *f){ if(t==f) t->cf=f; else if(find(t)!=find(f)) link(f,t); else makeroot(t),t->cf=f;}inline void change(M *t,M *f){ M *r=find(t); if(r->cf==NULL) cut(t),add(t,f); else{ if(r==t) t->cf=NULL,add(t,f); else{ M *cir=r->cf; cut(t);add(t,f); if(find(r)!=find(cir)) r->cf=NULL,link(cir,r); } }}signed main(void){ scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) tr[i]=M(); for(int i=1;i<=n;i++) scanf("%d",&p[i]),p[i]+=i,add(tr+i,tr+(((p[i]>n)||(p[i]<1))?0:p[i])); for(int q=1,opt,x,y;q<=m;q++){ scanf("%d",&opt); if(opt==1){ scanf("%d",&x); M *r=find(tr+x); if(r->cf==NULL) makeroot(tr+0),access(tr+x),splay(tr+x),printf("%d\n",tr[x].dis-1); else puts("-1"); } else{ scanf("%d%d",&x,&y);p[x]=y+x; change(tr+x,tr+(((p[x]>n)||(p[x]<1))?0:p[x])); } } return 0;}
By NeighThorn
BZOJ 4764: 弹飞大爷
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。