2002: [Hnoi2010]Bounce 弹飞绵羊 - #include <Seter> - using namespace Orz;
2002: [Hnoi2010]Bounce 弹飞绵羊
http://www.zybbs.org/JudgeOnline/problem.php?id=2002
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 179464 | Seter | 2002 | Accepted | 6516 kb | 704 ms | C/Edit | 1803 B | 2011-12-19 12:46:33 |
终于写出LCT了……以前一直觉得LCT好难，现在发现原因是那时候我还没怎么用过splay。用SplayA掉一些题目以后再来看LCT，发现LCT实在是太简单了！从开始写（splay拷了自己的模板）到提交1A，总共才10+分钟！
然后开始无爱的刷Rank……不过失败了……ym7k+的122次提交……我不会告诉别人你是用O3的代码反汇编出来再交asm的 =。=
其实LCT的核心就是Access操作，即打通一个点到根的路径（且这条路径不能向下延伸），然后就可以处理这个点到某个祖先的路径上的询问了。具体操作就是实边和虚边的互相转化，杨哲等人的论文还是讲得很清楚的……这里不讲了。
如果是i,j两点间路径，那么需要求LCA。这时可以让access返回最后一次link操作时的父亲，那么access(i)后access(j)返回的就是LCA的指针了。
如果你不会Splay，那你最多只能大致了解LCT。如果你觉得你会Splay但是还没有A过题，那你想写LCT是非常困难的。想熟练快速并且悠闲地打出一个LCT模板，那么至少用SplayA掉2种（普通平衡树/代替线段树），每种2道不同类型的题目。
一般的LCT甚至不用Rank/Find等操作。比如这题只需要splay和Access两个操作即可！几乎不用花什么脑筋！
顺便牢骚一句，除了IO优化以外的任何刷RANK手段都是无耻的！！！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include <stdio.h>#define maxn 200000typedef struct _Splay{struct _Splay *c[2],*f,*p;int s;}Splay,*PSplay;Splay null,st[maxn];char str[1500000],*p=str,out[400000],*o=out;inline PSplay updt(PSplay x){if(x!=&null)x->s=x->c[0]->s+x->c[1]->s+1;return x;}inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}inline PSplay node(PSplay x,PSplay p){x->f=x->c[0]=x->c[1]=&null;x->s=1;x->p=p;return x;}inline PSplay rot(PSplay x){ PSplay fx=x->f,ffx=fx->f; _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx; if((x->f=ffx)!=&null)ffx->c[fc]=x; updt((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x,PSplay p){ if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return updt(x);}inline getint(){ int re=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}inline PSplay Access(PSplay x){ PSplay t=splay(x,&null);x->c[1]=x->c[1]->f=&null; while((x=splay(extr(x,0),&null))->p!=&null){ splay(x->p,&null)->c[1]->f=&null; x=(x->p->c[1]=x)->f=x->p; }return t;}inline void print(x){ char buf[10],*b=buf; while(x)*b++=x%10+48,x/=10; while(b--!=buf)*o++=*b; *o++='\n';}main(){ int n,i=-1,x,k,t;fread(p,1,1500000,stdin); null.f=null.c[0]=null.c[1]=&null; for(n=getint();++i!=n;node(st+i,i+(k=getint())>=n?&null:st+i+k)); for(t=getint();t--;)if(getint()==1)print(splay(Access(st+getint()),&null)->c[0]->s+1); else{ splay(st+(x=getint()),&null)->c[0]->f=&null; st[x].c[0]=&null; updt(updt(st+x)->p=x+(k=getint())>=n?&null:st+x+k); }*--o=0;return puts(out),0;} |
下面是些无关的话题：
1.我真心写不出LCT的模板啊……谁来告诉我除了Access还有啥操作？
2.今天数学课上突然弄懂了DC3（Skew）算法……太他妈神奇了，什么时候一定要去试试！
3.我觉得代码短看起来爽啊……我一开始不会LCT很可能和某些80行以上的超长代码有关……我会想，LCT这么长，我肯定学不会……
上面那个其实不是标准的LCT……又写了标准的……就是每个点只记录一个父亲的，然后一条链的splay中的根的父亲是这条链的最上面那个点的真实父亲。
这样弄了以后发现有点晕……两题调了我6小时，然后这题发现是有一句代码的执行顺序在本地和OJ上不同导致TLE……洞穴勘测那题发现是少了个pushdown……欲哭无泪啊……
洞穴勘测那题是好题，就是数据太委了，暴力就能过……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <stdio.h>#define maxn 200000typedef struct _Splay{struct _Splay *c[2],*f;int s;}Splay,*PSplay;Splay null,st[maxn];char str[1500000],*p=str,*o=str;inline PSplay fa(PSplay x){return x->f->c[0]==x||x->f->c[1]==x?x->f:&null;}inline PSplay updt(PSplay x){x->s=x->c[0]->s+x->c[1]->s+1;return x;}inline PSplay node(PSplay x,PSplay f){x->f=f;x->c[0]=x->c[1]=&null;x->s=1;return x;}inline PSplay rot(PSplay x){ PSplay fx=fa(x),ffx=fa(fx); _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ x->f=fx->f; if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx; if(ffx!=&null)ffx->c[fc]=x; updt((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x,PSplay p){ PSplay fx,ffx;if(x==&null)return x; for(;(fx=fa(x))!=p;rot(x))if((ffx=fa(fx))!=p)rot((ffx->c[1]==fx)==(fx->c[1]==x)?fx:x); return updt(x);}inline getint(){ int re=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}inline PSplay Access(PSplay x){ PSplay t=&null,y=x; while(splay(x,&null)->c[1]=t,x->f!=&null)x=(t=updt(x))->f; return splay(y,&null);}inline void print(x){ char buf[10],*b=buf; while(x)*b++=x%10+48,x/=10; while(b--!=buf)*o++=*b; *o++='\n';}main(){ int n,i=-1,x,k,t;fread(p,1,1500000,stdin); null.f=null.c[0]=null.c[1]=&null; for(n=getint();++i!=n;node(st+i,i+(k=getint())>=n?&null:st+i+k)); for(t=getint();t--;)if(*++p==49)p++,print(Access(st+(x=getint()))->c[0]->s+1); else if(*p==50){ p++;Access(st+(x=getint()))->c[0]->f=&null;st[x].c[0]=&null; updt(st+x)->f=x+(k=getint())>=n?&null:st+x+k; }else t++;*--o=0;return puts(str),0;} |
By Seter
2012年2月21日 08:44
LCT1200+B水过。。。
2012年2月21日 16:20
ym神犇