首页 > 代码库 > BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊 LCT
BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊 LCT
这道题的lct不想说什么......
这道题是lct的假板子题你需要精简并适当改进LCT给他加上不清真的属性......
#include<cstdio> #include<cstring> #define MAXN 200010 using namespace std; struct spaly { spaly *ch[2],*f; int size; void pushup() { size=ch[1]->size+ch[0]->size+1; } }null[MAXN]; int n,m,a[MAXN]; inline int get(spaly *p) { return p->f->ch[1]==p; } inline bool isroot(spaly *p) { return p->f->ch[0]!=p&&p->f->ch[1]!=p; } inline void rotate(spaly *p) { spaly *fa=p->f,*pa=fa->f; int j=get(p); if(!isroot(fa))pa->ch[get(fa)]=p; if((fa->ch[j]=p->ch[j^1])!=null)fa->ch[j]->f=fa; fa->f=p; p->f=pa; p->ch[j^1]=fa; fa->pushup(); p->pushup(); } inline void Spaly(spaly *p) { for(spaly *fa=p->f;!isroot(p);rotate(p),fa=p->f) if(!isroot(fa)) rotate(get(fa)==get(p)?fa:p); } inline void expose(spaly *p) { spaly *y=null; while(p!=null) { Spaly(p); p->ch[1]=y; p->pushup(); y=p; p=p->f; } } inline void link(spaly *x,spaly *y) { Spaly(x); x->f=y; } inline void cut(spaly *x,spaly *y) { expose(x); Spaly(x); x->ch[0]->f=null; x->ch[0]=null; x->pushup(); } inline void Init() { scanf("%d",&n); null->ch[0]=null->ch[1]=null->f=null; for(int i=1;i<=n;i++) null[i].ch[0]=null[i].ch[1]=null[i].f=null,null[i].size=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(i+a[i]<=n)link(null+i,null+i+a[i]); } } inline void work() { scanf("%d",&m); while(m--) { int opt; scanf("%d",&opt); int x,y; if(opt==1) { scanf("%d",&x); x++; expose(null+x); Spaly(null+x); printf("%d\n",null[x].size); } else { scanf("%d%d",&x,&y); x++; expose(null+x); Spaly(null+x); if(null[x].size!=1)cut(null+x,null+x+a[x]); a[x]=y; if(x+y<=n)link(null+x,null+x+y); } } } int main() { Init(); work(); return 0; }
BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊 LCT
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。