洛谷P3203 [HNOI2010]弹飞绵羊(LCT,Splay)

洛谷题目传送门关于LCT的问题详见思路分析首先分析一下题意。对于每个弹力装置,有且仅有一个位置可以弹到。把这样的一种关系可以视作边。
然后,每个装置一定会往后弹,这不就代表不存在环么?
于是,一个森林的模型被我们建出来了。
考虑到有修改弹力值的操作,也就是要断边和连边,于是用LCT维护。思路一每一个点向它弹到的位置连边。如果被弹飞了,那么这条边就不存在。
查询弹飞的步数,就是查询该点到其所属原树中根节点的路径的(size)
注意此题的一些特性。我们并不需要查询或者更改指定路径((x-y))的信息。
也就是说,我们根本不需要换根!
原来需要换根的(split,link,cut)操作,我们可以根据题目特性适当调整一下。
  • 查询原本需要(split),我们直接(access(x),splay(x)),输出(x)(size)
  • 连边原本需要(link),题目保证了是一棵树,我们直接改(x)的父亲,连轻边。
  • 断边原本需要(cut),然而我们确定其父亲的位置,(access(x),splay(x))后,(x)的父亲一定在(x)的左子树中(LCT总结中的性质1),直接双向断开连接。
  • 然后我们发现,程序一下子少了一堆函数((pushdown,makeroot,findroot,split,link,cut)
    代码少,常数小,何乐而不为?
    下面贴代码
    #include<cstdio>
    #include<cstdlib>
    #define R register int
    #define I inline void
    #define G ch=getchar()
    #define gc G;while(ch<'-')G
    #define in(z) gc;z=ch&15;G;while(ch>'-')z*=10,z+=ch&15,G;
    const int N=200009;
    int f[N],c[N][2],s[N];
    bool r[N];
    inline bool nroot(R x){
        return c[f[x]][0]==x||c[f[x]][1]==x;
    }
    I pushup(R x){
        s[x]=s[c[x][0]]+s[c[x][1]]+1;
    }
    I rotate(R x){
        R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
        if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
        if(w)f[w]=y;f[y]=x;f[x]=z;
        pushup(y);
    }
    I splay(R x){
        R y,z;
        while(nroot(x)){
            y=f[x];z=f[y];
            if(nroot(y))
                rotate((c[y][0]==x)^(c[z][0]==y)?y:x);
            rotate(x);
        }
        pushup(x);
    }
    I access(R x){
        for(R y=0;x;x=f[y=x])
            splay(x),c[x][1]=y,pushup(x);
    }//以上是轻量化的LCT板子
    int main()
    {
        register char ch;
        R n,m,j,k;
        in(n);
        for(j=1;j<=n;++j){
            s[j]=1;
            in(k);
            if(j+k<=n)f[j]=j+k;//如果弹飞了就不连边
        }
        in(m);
        while(m--){
            gc;
            if(ch&1){
                in(j);++j;
                access(j);splay(j);//直接查询
                printf("%dn",s[j]);
            }
            else{
                in(j);in(k);++j;
                access(j);splay(j);
                c[j][0]=f[c[j][0]]=0;//直接断边
                if(j+k<=n)f[j]=j+k;//直接连边
                pushup(j);
            }
        }
        return 0;
    }
    思路2把弹飞这种情况也可以视作一个节点(编号可定为(n+1)
    如果弹飞了就把(x)连到这个点上,于是这个点稳稳地坐住了树根的位置。
    查询的时候得到的(size)(1)即可。
    其它同上。
    其实个人认为这样不如上面。动态树本身就定义为维护森林,多了这一个点等于强行把它变成一棵树,可能有点多此一举。。。。。。
    代码如下,只贴main函数,因为LCT板子是一样的。。。。。。
    int main()
    {
        register char ch;
        R rt,n,m,j,k;
        in(n);rt=n+1;
        for(j=1;j<=rt;++j)s[j]=1;
        for(j=1;j<=n;++j){
            in(k);
            f[j]=j+k>n?rt:j+k;//与上面不同
        }
        in(m);
        while(m--){
            gc;
            if(ch&1){
                in(j);++j;
                access(j);splay(j);
                printf("%dn",s[j]-1);
            }
            else{
                in(j);in(k);++j;
                access(j);splay(j);
                c[j][0]=f[c[j][0]]=0;
                f[j]=j+k>n?rt:j+k;
                pushup(j);
            }
        }
        return 0;
    }

    相关内容推荐