基于圆方树的动态仙人掌

圆方树好妙啊 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