首页 > 代码库 > 【BZOJ】2002: [Hnoi2010]Bounce 弹飞绵羊（lct）
【BZOJ】2002: [Hnoi2010]Bounce 弹飞绵羊（lct）
（BZOJ挂了，还没在BZOJ测，先是在wikioi测过了，，）
囧。在军训时立志要学lct！！！这是一道lct的裸题，只有access操作（10行都没有啊亲。。。缩行大法的话，我就不说了。。）（link操作相当于水过），其实lct很简单。。想想都有点小激动。。。。。。
lct用splay维护的话，一下就写好了。。但是我在写lct的时候，发现了一些我原来splay的老问题，我原来也知道了的，就是将null的ch给赋值了，因为在rot操作里没有特判，所以导致了null的孩子被赋值了，导致我的lct调试了2天T_T
这不科学啊！！（但是想想了还好了，，因为lct在splay的过程中，是有父亲而父亲不一定有这个孩子的，因为lct维护的是森林。。所以在splay里有加特判，即父亲是否有这个孩子
还有个地方卡了我的调试，就是access操作，本来我是没有加ch[1]->f=null的，之前调试的时候以为是这里出问题，但是证明我很蠢。。。。这里一定不能这样搞啊！因为这样就将孩子和父亲断了联系。。。囧。
本题有个特性，即已经有序了的，我们可以从后往前看这个数组，想象成森林，某根的孩子就是在原数组的左边（深度比他深，即越后的元素深度越浅，因为lct在找preferred path的时候splay是按深度构图的，那么孩子就是在父亲的左边，而羊是从左往右走的，所以在更新的时候，不能断了左边的联系T_T，就是我之前的那个错误。。。。将孩子的父亲断了。。T_T。）
link-cut tree具体看论文吧，很容易看懂的，真心话。就是用一颗splay维护某个点的路径，即access操作，我相信多做题就行了的
。。找到错误真开心～调试出来了真开心～
有时间在学习完整套lct然后写篇专题。。囧。。最近看的数学真心感觉有点难啊，数论怎么那么hentai啊？公式推来推去就是为了将O(n)变成O(1)么。这东西能在考场上想到吗囧。好吧，我是蒟蒻所以想不到。
#include <cstdio>#define read(x) x=getint()using namespace std;inline int getint() { char c; int ret=0; for(c=getchar(); c<‘0‘ || c>‘9‘; c=getchar()); for(; c>=‘0‘ && c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return ret; }const int N=200005;struct node* null;struct node { node *f, *ch[2]; int s; void pushup() { s=1+ch[0]->s+ch[1]->s; } bool d() { return f->ch[1]==this; } void setc(node* c, bool d) { ch[d]=c; c->f=this; } bool check() { return f==null || (f->ch[0]!=this && f->ch[1]!=this); } //check操作是lct特地的，因为为了省空间，我们不开n颗splay，只用节点关联就行了，这样就无法避免父亲没有这个孩子的情况。所以还要特判}*nd[N];void rot(node* r) { node* f=r->f; bool d=r->d(); if(f->check()) r->f=f->f; else f->f->setc(r, f->d()); //这里一定要这样写，不然会让null的孩子改变，这样在splay的循环就会死循环T_T f->setc(r->ch[!d], d); r->setc(f, !d); f->pushup();}inline void splay(node* r) { while(!r->check()) if(r->f->check()) rot(r); else r->d()==r->f->d()?(rot(r->f), rot(r)):(rot(r), rot(r)); r->pushup();}inline void access(node* f) { for(node* c=null; f!=null; f=f->f) { splay(f); f->setc(c, 1); f->pushup(); c=f; }}inline void link(node* c, node* f) { access(c); splay(c); c->ch[0]->f=null; c->ch[0]=null; c->f=f; c->pushup();}inline void init() { null=new node; null->s=0; null->f=null->ch[0]=null->ch[1]=null;}int main() { init(); int n, t; read(n); for(int i=0; i<n; ++i) { nd[i]=new node; nd[i]->s=1; nd[i]->ch[0]=nd[i]->ch[1]=nd[i]->f=null; } for(int i=0; i<n; ++i) { read(t); if(i+t<n) nd[i]->f=nd[i+t]; } int m, a, b, c; read(m); for(int i=0; i<m; ++i) { read(a); read(b); if(a==1) { access(nd[b]); splay(nd[b]); printf("%d\n", nd[b]->s); } else { read(c); if(b+c<n) link(nd[b], nd[b+c]); else link(nd[b], null); } } return 0;}