题解【P8265 [Ynoi Easy Round 2020] TEST_63】

jerry3128 · 2022-04-02 11:15:19 · 题解

题目大意：维护动态树上带第二关键字比较的重链剖分。

• 轻重边描述的是重链剖分，虚实边描述的是 LCT。
• 复杂度的描述会形如 （外置信息操作+虚实切换用时+查询）
• 考虑一个比较容易证明的事实，对于一次 link-cut 操作前后的树的链剖形态，一条边轻重切换的代价为一，则总代价不会超过 \mathcal O(\log n) 级别。
• 所以我们考虑用 LCT 的虚实边结构直接维护原树剖的轻重剖分结构。具体的我们直接对 LCT 操作，最后在询问之前将需要从虚实与轻重不匹配的边操作掉就行了。然后这些操作在外映射的一个数据结构上面用于求第 k 大。
• 所以问题现在变为了“如何求到一条链上，应该从实边变成虚边的一条边”。我们考虑一条重边，其指向节点的子树大小应该为最大的点。所以我们靠考虑维护差量 val=mxgsz-sz_{rs} 即最大虚儿子大小减去右儿子大小。考虑 LCT 上一个 splay 只关系到其子结构的信息，所以如果一个 splay 节点不是 splay 根节点，它的信息是不完整的。所以我们转移时需要判定右儿子对左儿子的贡献。记录子树最大的 val，判定其是不是正数即可。第二关键字一样的，但是码量大了几倍（
• 考虑换根，你反着维护一套信息就行了。
• 那么现在就维护来看就出现了两种方法。

1. 信息由下向上传递，信息来源由上往下查找。

   • 因为我们对一个边的虚实切换仍然要往下找到那个点，而且不用维护信息来源，是小常数的好选，也是我的实现方式。
   • 但是信息来源的查找相当于做一个跨越虚边 search 的过程，这需要不少的使用技巧，否则复杂度可能劣化。
   • 你可以考虑用 set 记录每个节点虚儿子的链顶，以及其子树信息，在做 search 的时候你 splay 一个链顶然后递归处理实链，由下至上依次做。复杂度 \mathcal O(m\log^{2}n+m\log^{2}n+m\log n)
   • 或者使用 Top-Tree 的技巧直接优化，这样就没有 set 记录子树信息，并且跨越虚边的信息查找可以直接跳跃，也就是我的实现方法。复杂度 \mathcal O(m\log^{2}n+m\log n+m\log n)，发现可以多叉摊一下到 \mathcal O(m\log n \log_{\omega}n+m\log n + m\omega\log_{\omega}n)。

2. 信息由下向上传递，信息来源一起上传。

   • 这种方法信息维护常数比较大，我不觉得能赶过去。（？
   • 你把信息来源压入 val，一起上传然后直接在树根检索其 val 直到没有非法 val 停止检索。
   • 时间复杂度 \mathcal O(m\log^{2}n+m\log^{tmp^{(1)}}n+m\log n)。(1) 无法证明 tmp=1 或 tmp=2 或 tmp=3。

关键代码

//ayanami保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
const pair<int,int> zero=make_pair(0,0);
int max(int a,int b,int c){return max(a,max(b,c));}
pair<int,int> max(pair<int,int> a,pair<int,int> b,pair<int,int> c){return max(a,max(b,c));}
int n,m;
pair<int,int> operator -(pair<int,int> a,pair<int,int> b){return make_pair(a.first-b.first,a.second-b.second);}
namespace T{
    int tot,sta[200005];
    struct node{
        int ch[3],fa,pre,suf,rev,mx,sz,ans,vmx,rmx,now;pair<int,int> val,ral,gal;
        void insval(pair<int,int> V,int M){if(val.first<V.first||(val.first==V.first&&(val.second+vmx)<(V.second+M)&&V.second>0))val=V,vmx=M;}
        void insral(pair<int,int> V,int M){if(ral.first<V.first||(ral.first==V.first&&(ral.second+rmx)<(V.second+M)&&V.second>0))ral=V,rmx=M;}
    }v[200005];
    void push_up(int rt){
        if(!rt)return;
        if(rt<=n){
            v[rt].pre=v[rt].ch[0]?v[v[rt].ch[0]].pre:rt;
            v[rt].suf=v[rt].ch[1]?v[v[rt].ch[1]].suf:rt;
            v[rt].mx=max(v[v[rt].ch[0]].mx,v[v[rt].ch[1]].mx,rt);
            v[rt].sz=v[v[rt].ch[0]].sz+v[v[rt].ch[2]].sz+1+v[v[rt].ch[1]].sz;

            v[rt].val=v[rt].ral=zero,v[rt].vmx=v[rt].rmx=0;
            v[rt].insval(v[v[rt].ch[1]].val,v[v[rt].ch[1]].vmx);
            v[rt].insval(v[v[rt].ch[2]].ral-make_pair(v[v[rt].ch[1]].sz,v[v[rt].ch[1]].mx),v[v[rt].ch[1]].mx);
            v[rt].insval(v[v[rt].ch[0]].val-make_pair(v[rt].sz-v[v[rt].ch[0]].sz,max(max(rt,v[v[rt].ch[1]].mx)-v[v[rt].ch[0]].vmx,0)),max(v[v[rt].ch[0]].vmx,rt,v[v[rt].ch[1]].mx));
            v[rt].insral(v[v[rt].ch[0]].ral,v[v[rt].ch[0]].rmx);
            v[rt].insral(v[v[rt].ch[2]].ral-make_pair(v[v[rt].ch[0]].sz,v[v[rt].ch[0]].mx),v[v[rt].ch[0]].mx);
            v[rt].insral(v[v[rt].ch[1]].ral-make_pair(v[rt].sz-v[v[rt].ch[1]].sz,max(max(rt,v[v[rt].ch[0]].mx)-v[v[rt].ch[1]].rmx,0)),max(v[v[rt].ch[1]].rmx,rt,v[v[rt].ch[0]].mx));

            v[rt].gal=max(v[v[rt].ch[0]].gal,v[v[rt].ch[1]].gal,v[v[rt].ch[2]].val);
            v[rt].ans=v[v[rt].ch[0]].ans^rt^v[v[rt].ch[1]].ans;
        }else{
            v[rt].sz=v[v[rt].ch[0]].sz+v[v[rt].ch[1]].sz+v[v[rt].ch[2]].sz;
            v[rt].ral=max(v[v[rt].ch[0]].ral,v[v[rt].ch[1]].ral,make_pair(v[v[rt].ch[2]].sz,v[v[rt].ch[2]].mx));
            v[rt].val=max(v[v[rt].ch[0]].val,v[v[rt].ch[1]].val,max(v[v[rt].ch[2]].val,v[v[rt].ch[2]].gal));
        }
    }
    int gt;
    int searchm(int x){
        push_down(x);
        if(v[x].ch[2]&&v[x].ral==make_pair(v[v[x].ch[2]].sz,v[v[x].ch[2]].mx))return x;
        if(v[x].ch[0]&&v[x].ral==v[v[x].ch[0]].ral)return searchm(v[x].ch[0]);
        if(v[x].ch[1]&&v[x].ral==v[v[x].ch[1]].ral)return searchm(v[x].ch[1]);
        return 0;
    }
    int searchc(int x){
        push_down(x);
        if(v[x].ch[1]&&v[x].val==v[v[x].ch[1]].val)return searchc(v[x].ch[1]);
        if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].ral-make_pair(v[v[x].ch[1]].sz,v[v[x].ch[1]].mx))return gt=x,searchm(v[x].ch[2]);
        if(v[x].ch[0]&&v[x].val==v[v[x].ch[0]].val-make_pair(v[x].sz-v[v[x].ch[0]].sz,max(max(x,v[v[x].ch[1]].mx)-v[v[x].ch[0]].vmx,0)))return searchc(v[x].ch[0]);
        return 0;
    }
    int searchg(int x){
        push_down(x);
        if(x<=n){
            if(v[x].gal<=zero)return 0;
            if(v[x].ch[2]&&v[x].gal==v[v[x].ch[2]].val)return searchg(v[x].ch[2]);
            if(v[x].ch[1]&&v[x].gal==v[v[x].ch[1]].gal)return searchg(v[x].ch[1]);
            if(v[x].ch[0]&&v[x].gal==v[v[x].ch[0]].gal)return searchg(v[x].ch[0]);
        }else{
            if(v[x].val<=zero)return 0;
            if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].val)return searchc(v[x].ch[2]);
            if(v[x].ch[0]&&v[x].val==v[v[x].ch[0]].val)return searchg(v[x].ch[0]);
            if(v[x].ch[1]&&v[x].val==v[v[x].ch[1]].val)return searchg(v[x].ch[1]);
            if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].gal)return searchg(v[x].ch[2]);
        }
        return 0;
    }
    void solve(int x){int g=0;splay(x);while((v[x].val>zero&&(g=searchc(x)))||(v[x].gal>zero&&(g=searchg(x))))splice(g),pre_push_up(gt),splay(x);}
}