UOJ Logo AwD的博客

博客

基于圆方树的动态仙人掌

2017-02-06 07:02:50 By AwD

圆方树好妙啊 orz orz

感觉用圆方树实现比vfk博客中的实现方法方便多了QAQ

很早就在uoj的博客上看到了圆方树orz,学习了以后就去尝试实现LCC。

重温代码写出来的东西可能会出现一些偏差QAQ

第一次写博客,见谅QAQ

核心思想是用一个结构去维护每个环,大致像这样:

cactus1

灵魂画师QAQ

这是什么意思呢?

考虑一条重链上的环,令这环与重链的交点为X、 Y,其中X为深度低的那个。

那么这个环就被分成了两条链 L、R,这个可以当做重链一样维护。

为了方便维护,我们设立新点Y',它用来表示Y在拆下X后形成的链中的位置,可以看作圆方树中的方点,总之就是来标识环的

如果开一个新指针cir,就可以在LCT的基础上存下环了(图中的箭头就是这条指针

为了方便,我们称有该指针的点为环点,否则为树点

那么基于圆方树的LCC的每个节点长这样(以下代码都以 uoj 63 为例

struct node
{
    int ch[2], fa;
    int rev;
    int tp;
    int dis, sum_dis;
    int cir, sum_cir;
} tr[N];

其中tp代表这个点的属性,1表示实点,0表示虚点(即Y')

这样很容易就可以写出update函数和rotate函数:

void update(int t)
{
    if (!tr[t].tp)
    {
        tr[t].sum_dis = tr[tr[t].ch[0]].sum_dis + tr[tr[t].ch[1]].sum_dis + tr[t].dis + tr[tr[t].cir].sum_dis;
        tr[t].sum_cir = tr[tr[t].ch[0]].sum_cir + tr[tr[t].ch[1]].sum_cir + tr[tr[t].cir].sum_cir;
    }
    else
    {
        tr[t].sum_dis = min(tr[tr[t].ch[0]].sum_dis, tr[tr[t].ch[1]].sum_dis);
        tr[t].sum_cir = min(tr[tr[t].ch[0]].sum_cir, tr[tr[t].ch[1]].sum_cir) + 1;
    }
}
void rotate(int t)
{
    int k = is_right(t), b = tr[t].ch[!k], a = tr[t].fa, o = tr[a].fa;
    tr[a].ch[k] = b; tr[t].ch[!k] = a; 
    if (!is_root(a)) tr[o].ch[is_right(a)] = t;
    else if (tr[o].cir == a) tr[o].cir = t;
    if (b) tr[b].fa = a; tr[a].fa = t; tr[t].fa = o;
    update(a); update(t);
}

现在考虑reverse操作,树点和LCT一样做,环点只要这样就行了:(雾

cactus2

大概长这样:

void reverse(int t)
{
    swap(tr[t].ch[0], tr[t].ch[1]);
    if (tr[t].cir) swap(tr[tr[t].cir].ch[0], tr[tr[t].cir].ch[1]);
    tr[t].rev ^= 1;
}

现在重头系来了,access操作。

树点依然和LCT一样做,只需考虑环点。

考虑这个操作的本质,对于a的重孩子b和轻孩子c,那么如果对c做access操作,就相当于交换b和c在LCT中的地位,对于LCC也一样

如果要交换t和r在环上的位置,那么就相当于这样:

cactus3

(最右边的箭头上应该是t,莫名其妙消失了QAQ

r进入环中,t变成o的后继,并依次修改环上的信息。

容易发现这样并不会破坏LCC的结构,因此是可行的。

具体实现的话这样做

1.交换r与额外点a的位置

2.将t splay至o的cir

3.交换额外点a与t的位置

就好了

代码长这样:(不知道为啥写了递归版本的,稍微有一点鬼畜QAQ

int ancestor(int t)
{
    if (!is_root(t)) return ancestor(tr[t].fa); else return t;
}
void dfs(int t)
{
    int a = ancestor(t), o = tr[a].fa;
    if (o) 
    {
        dfs(o);
        if (!tr[a].tp)
        {
            tr[o].ch[1] = a;
            update(o);
            splay(t, EMP);
        }
        else
        {
            int r = find(tr[o].ch[1], 0); splay(r, tr[o].ch[1]);
            if (tr[a].ch[0]) tr[tr[a].ch[0]].fa = r;
            if (tr[a].ch[1]) tr[tr[a].ch[1]].fa = r;
            tr[o].cir = r;
            tr[r].ch[0] = tr[a].ch[0]; tr[r].ch[1] = tr[a].ch[1];
            tr[o].ch[1] = 0;
            update(r);
            splay(t, EMP);
            if (tr[t].ch[0]) tr[tr[t].ch[0]].fa = a;
            if (tr[t].ch[1]) tr[tr[t].ch[1]].fa = a;
            tr[o].cir = a;
            tr[a].ch[0] = tr[t].ch[0]; tr[a].ch[1] = tr[t].ch[1];
            tr[t].fa = o;
            tr[t].ch[0] = 0; tr[t].ch[1] = 0; tr[o].ch[1] = t;
            update(a); update(t); update(o);
            rotate(t);
        }
    }
    else splay(t, EMP);
}
void access(int t)
{
    push_it(t);
    dfs(t);
    tr[t].ch[1] = 0;
}

然后就好啦?

什么,你说link和cut?这个只要稍微yy一下就好啦~(其实是懒啦,我都不知道当时在写啥~

link出环的时候,只要添个额外点,然后再把那一段链全部塞到左子数树就行了

cut环的时候,只要把额外点代表的点拎出来,替换掉额外点就行了,具体见代码吧~

具体实现的时候……到处都是细节

不过很好写呢,而且有很强的扩展性,原版LCC能做的东西它都能做~

时间复杂度似乎是$O(m log ^2(n))$的,我不会势能分析啥的QAQ

代码:

http://uoj.ac/submission/93117

http://uoj.ac/submission/93126

http://uoj.ac/submission/93536

是不是很短?QAQ

另安利一题233:

http://www.lydsy.com/JudgeOnline/problem.php?id=4683

用同样的思想维护两个环套起来的东西,然后就可以搞了,是不是听上去很简单(捂脸

完结?撒花!

评论

xrdog
资瓷啊,但是您的图似乎显示不出来欸。。
frank_c1
前排资瓷!
immortalCO
orz!前排资磁!
ddd
你这个和圆方树有什么关系啊,关系是命名圆方树的人到这底下回了一句么
frank_c1
妙啊!
fuckshitman
van♂dark♂load
ez_zwl
妙不可言

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。