题解 P8262【[CTS2022] WBTT】

FunnyCreatress · 2022-05-08 21:48:47 · 题解

青蛙nb。

先来考虑一个弱化的问题：给你一个序列，每次交换相邻两段，用造出来的集合表示区间，合并信息代价是集合大小之和。

这个东西满脸写着不可 \mathrm{polylog}，所以考虑块状链表，然而重构的时候需要分治，这样单次是 O(\sqrt{n\log n}) 的，点名被卡。

然后我们发现我们没有什么思路，于是尝试破解标题。~~然后误打误撞搞出了一个另解~~

\mathrm{WBTT=Weight\ Balanced\ Ternary\ Tree}

具体来说，我们对每个块维护的是一棵三叉树，满足对于每个节点，每棵子树的大小不超过当前子树的一半。我们需要支持分裂以及合并操作。

先来合并操作：

我们现在要合并蓝红两棵树，不妨设蓝树比红树小，那么显然有蓝树和红树的左子树和红子树的中右子树中必有一种合法的合并方案，递归合并，设总大小为 S，复杂度为

T(S)=O(S)+T(\dfrac S2)=O(S)

然后是分裂操作。这个其实有了合并操作就不是问题了，先递归进分裂点所在子树，然后把分出来的两棵树分别与左右合并就行。复杂度也是 O(S) 的。

这里先给出 WBTT 的实现。

namespace wbtt{
    int stk[N*5],tp,cntn;
    struct node{
        int ls,ms,rs;infoset v;
        node(){v=emptyset,ls=ms=rs=0;}
        node(int x){v=info[x],ls=ms=rs=0;}
        int size(){return v.size();}
    } T[N*5];
    int newnode(){return tp?stk[tp--]:++cntn;}
    void recyc(int x){T[x]=node(),stk[++tp]=x;}
    int merge(int x,int y){
        if(T[x].size()==0||T[y].size()==0)return x+y;
        if(T[x].size()==1&&T[y].size()==1){int p=newnode();T[p].ls=x,T[p].ms=y,T[p].v=merge(T[x].v,T[y].v);return p;}
        if(T[x].size()<=T[y].size()){
            T[y].v=merge(T[x].v,T[y].v);
            if(T[x].size()+T[T[y].ls].size()<=(T[y].size()>>1))return T[y].ls=merge(x,T[y].ls),y;
            else return T[y].rs=merge(T[y].ms,T[y].rs),T[y].ms=T[y].ls,T[y].ls=x,y;
        }
        else{
            T[x].v=merge(T[x].v,T[y].v);
            if(T[T[x].rs].size()+T[y].size()<=(T[x].size()>>1))return T[x].rs=merge(T[x].rs,y),x;
            else return T[x].ls=merge(T[x].ls,T[x].ms),T[x].ms=T[x].rs,T[x].rs=y,x;
        }
    }
    pair<int,int> split(int x,int p){
        if(p==T[x].size())return make_pair(x,0);
        if(p==0)return make_pair(0,x);
        if(p<=T[T[x].ls].size()){
            pair<int,int> res=split(T[x].ls,p);
            res.second=merge(merge(res.second,T[x].ms),T[x].rs);
            return recyc(x),res;
        }
        if(p<=T[T[x].ls].size()+T[T[x].ms].size()){
            pair<int,int> res=split(T[x].ms,p-T[T[x].ls].size());
            res.first=merge(T[x].ls,res.first),res.second=merge(res.second,T[x].rs);
            return recyc(x),res;
        }
        pair<int,int> res=split(T[x].rs,p-T[T[x].ls].size()-T[T[x].ms].size());
        res.first=merge(T[x].ls,merge(T[x].ms,res.first));
        return recyc(x),res;
    }
    void build(int l,int r,int x,int *a){
        if(l==r){T[x]=node(a[l]);return;}
        int ml=(2*l+r)/3,mr=(l+2*r)/3;
        build(l,ml,T[x].ls=newnode(),a);
        if(ml!=mr)build(ml+1,mr,T[x].ms=newnode(),a);
        build(mr+1,r,T[x].rs=newnode(),a),T[x].v=merge(merge(T[T[x].ls].v,T[T[x].ms].v),T[T[x].rs].v);
    }
}

那么上树之后的事情就不难想了。我不知道随机撒点复杂度对不对，而复杂度正确的动态树分块实现过于复杂且常数较大，所以这里给出一个实现较为简单且常数较小的根号分治写法。

令 B=O(\sqrt n)，对子树大小做根号分治。对于子树大小大于 B 的点，显然它们会形成一棵类似虚树的东西。我们对虚树上的每条链维护一个块状链表，每个块维护块内的 WBTT，然后只要支持分裂合并这些基本操作就行。

对于子树大小不超过 B 的点，我们用 WBTT 维护子树的的轻重链剖分。然后需要实现几个操作：

剥离一棵子树：先把这棵子树切下来。显然只有切点所在重链会发生变化，自顶向下检查每个点的子树，如果发生变化就暴力切开重连。

复杂度证明：显然只需要考虑每次切割下半段的复杂度，而由于从是轻链转到重链所以切换的复杂度显然不超过新的重子树大小，而改变的所有重子树不交。
嫁接一棵子树：提前计算好哪些位置会发生变化，自底向上重构。最后再连上新的子树。复杂度证明和剥离操作类似。
把一条链换到虚树上：先把该切的地方切了，自底向上合并。

复杂度证明：每次跳重链子树大小至少翻倍，而重链长度显然不超过子树大小。
把虚树的一条链换出去：先算好要切的地方，自顶向下切，再连上应该连的地方。复杂度证明和换入操作类似。

最后就是需要一个能 O(\sqrt n)-O(1) 的维护深度和子树大小的结构了，感觉用块状链表维护 ETT 是较好的选择。

由于修改的常数相当大，所以可以逝量调小 B。

但即使是这种实现也轻松打破了我的码长记录，所以我的建议是写一点调一点，全写完再调肯定是吃不消的。。。~~std 似乎实现的非常简洁，不是很懂~~ 好像是 Top Tree 但是我不会。

完整代码不贴，要的私信。