欢迎光临
我们一直在努力

PLCT检查是什么[Luogu P3203] [HNOI2010]弹飞绵羊 (LCT维护链的长度)

//Luogu P3203 [HNOI2010]弹飞绵羊
//Jan,9th,2018
//LCT模板题II
#include<iostream>
#include<cstdio>
using namespace std;
long long read()

    while(isdigit(c))
    return x*f;
}
const int N=200000+100;
int n,m;
struct LCT
{
    int son[N][2],fa[N],lazy[N],mstack[N],top,size[N];
    inline bool isRoot(int x)
    {
        return x!=son[fa[x]][0] && x!=son[fa[x]][1];
    }
    inline void update(int x)
    {
        size[x]=size[son[x][0]]+size[son[x][1]]+1;
    }
    inline void mirror(int x)
    {
        lazy[x]=!lazy[x],swap(son[x][0],son[x][1]);
    }
    inline void pushDown(int x)

    inline void rotate(int x,int type)

    void splay(int x)

    }
    void Access(int x)
    {
        for(int t=0;x!=0;t=x,x=fa[x])
            splay(x),son[x][1]=t,fa[t]=x,update(x);
    }
    inline void MakeRoot(int x)
    {
        Access(x),splay(x);
        mirror(x);
    }
    inline void Link(int x,int y)//x翻为根连向y
    {
        MakeRoot(x);
        fa[x]=y;
    }
    inline void split(int x,int y)//y为根
    {
        MakeRoot(x);
        Access(y),splay(y);
    }
    inline void Cut(int x,int y)
    {
        split(x,y);
        son[y][0]=fa[x]=0;
        update(y);
    }
    int Query(int x)
    {
        MakeRoot(n+1);
        Access(x),splay(x);
        return size[x]-1;
    }
}lct;
int q[N];
int main()

        else

    }
    return 0;
}
赞(0)
未经允许不得转载:上海聚慕医疗器械有限公司 » PLCT检查是什么[Luogu P3203] [HNOI2010]弹飞绵羊 (LCT维护链的长度)

登录

找回密码

注册