[Code+#7]六元环

gxy001 · 2021-07-06 21:52:46 · 题解

题意首先可以转化为求笛卡尔树上大小为 4 的连通块个数（对应六元环的六个点为这四个点和最上面节点代表区间的右端点 +1，左端点 -1），但不能包含根节点（六元环不包含 0，n+1），用一个简单的 dp 求解就行了。

修改操作体现在笛卡尔树上其实就是上旋，容易发现，对于一条方向相同的链，一个点上旋到链顶只会产生 O(1) 的父子关系改变，也只会产生 O(1) 的 dp 数组的改变。

所以直接用 LCT 去维护就行了。

核心代码：

inline void upd(int x,int val){
    int l=ch[x][0],r=ch[x][1];
    cut(x,l),cut(x,r);
    v[x]+=val;
    while(fa[x]&&cmp(x,fa[x])){
        splay(x);
        if(s[x][0]){
            int fat=findnxt(x),h=fa[x];
            cut(h,x);
            if(d[x])link(h,l),l=fat;
            else link(h,r),r=fat;
            if(fa[fat]){
                int g=fa[fat];
                cut(g,fat),link(g,x);
            }
        }else{
            int fat=fa[x];
            cut(fat,x);
            if(d[x])link(fat,l),l=fat;
            else link(fat,r),r=fat;
            if(fa[fat]){
                int g=fa[fat];
                cut(g,fat),link(g,x);
            }
        }
    }
    link(x,l),link(x,r);
    if(!fa[x]) rt=x;
}