P8353 [SDOI/SXOI2022] 无处存储

P8353 [SDOI/SXOI2022] 无处存储题解

我把这题当作树分块的模板题来写。前置知识点：虚树，分块。

题意

洛谷 P8353 [SDOI/SXOI 2022] 无处存储

树上链加，树上链求和，强制在线。注意本题特殊的时空限制。

\(n \le 7\times 10^6,q \le 5 \times 10^4\)。

解法

这个做法是我自己想的细节，常数有点大。

首先注意到本题的空间只有 \(64\) 兆，只能开两个长度为 \(n\) 的三十二位数组。这样的话，我们只能开记录每个点权值的数组和每个点父节点的数组，连图都建不了。显然，正常写法的带 \(\log\) 的数据结构大部分都用不了（当然总有一些狠人能卡过去）。

这里采用树分块做此题。简单的说，就是在树上随机取 \(\sqrt n\) 个点，建虚树。对于点到关键点的路径视为散块，暴力；对于关键点到关键点的路径视为整块，整体处理。

我们先来看一个结论：在树上随机撒 \(B\) 个点，建立虚树后，每个点期望向上走 \(O(\frac{n}{B})\) 步后到达一个关键点。这个结论看着很自然。

证明

我们现在只考虑我们最初撒的 \(B\) 个点，则某个点为关键点的概率为 \(p= \frac{B}{n}, 0 \lt p \lt 1\)。设 \(u\) 的第 \(i\) 个祖先为最近关键祖先概率为 \(P_i\)。则有

\[P_0 = p \\ P_i = p (1-\sum _{j=0}^{i-1} P_j) \]

显然 $ P_1= (1-p) ^1 p,P_2 =(1-p)^2 p$。猜想 \(P_i = (1-p)^ip\)。

考虑数学归纳法，假设 \(P_k= (1-p)^k p\) 已经证明成立，现证明 \(P_{k+1} = (1-p)^{k+1}p\)。

\[\begin{align*} P_{k+1} &= p [1-\sum _{i=1} ^ {k} (1-p)^i p]\\&= p [1- \frac{(1-p)^{k+1}-1}{1-(1-p)} p]\\&=p (1-p) ^{k+1} \end{align*} \]

当 \(k=0\) 时，\(P_k= p(1-p)^k\) 显然成立。故 \(\forall k \in \mathbb{N} ，P_k =p(1-p)^k\)。

现求期望。

\[\begin{align*} E &= \sum _{i=0} ^ \infty i P_i \\&= \sum _{i=0} ^ \infty i (1-p)^i p\\&=p \sum _{i=0} ^ \infty i r ^i \; \; (r=1-p) \end{align*} \]

由 $ 0 \lt p \lt 1$，得 \(0 \lt r \lt 1\)。

已知几何级数 \(\sum \limits _{i=0} ^ \infty r^i = \frac{1}{1-r}\) （这个不知道请自行百度）。

对两边对 \(r\) 求导得 \(\sum \limits _{i=0} ^ \infty i r^{i-1} = \frac{1}{(1-r)^2}\)。

故 \(\sum \limits _{i=0} ^ \infty i r^i =\frac {r}{(1-r)^2}\)。

\[\begin{align*} E &= p \frac{r}{(1-r)^2}\\&= p \frac{1-p}{p^2} \\&= \frac{1-p}{p} \\&= \frac{n-B}{B}\\&= \frac{n}{B}-1 \\&= O( \frac{n}{B}) \end{align*} \]

证毕！

类似序列分块中同时会处理散块和整块，我们直接取 \(B= \sqrt n\)。实践中，由于散块常数比较大，\(B\) 一般会略大于 \(\sqrt n\)。

然后我们回到算法本身。我会使用一些 top cluster 的说法来方便描述，建议了解一下相关概念。实际上，我认为这就是一种 top cluster 的实现方式。

关于 top cluster

以下内容参考周欣的《浅谈一类树分块的构建算法及其应用》。

一个树簇（cluster）是树上的联通子图，有至多两个点和全树的其他位置连接。
这两个结点被称做界点。
不是界点的点被称做内点。
这两个界点之间的路径被称做簇路径。

一般为了方便会钦定根为界点。
深度较浅的界点成为上界点，深度较深的界点成为下界点。

在本文中，界点就是虚树上的关键点。我们钦定下界点属于该树簇而上界点不属于。

先考虑如何建虚树。由于不能有额外的空间，我们不能想一般的虚树那样 \(O(k \log n)\) 的建虚树。考虑 \(O(n)\) 建虚树。从每个点向上跳，对于经过的每一个点都打上标记。如果经过了某个之前打过标记的点，则说明该点为关键点的 LCA，应该存在于虚树中。特别的，为了方便，我们强制 \(1\) 为虚树的根。

然后预处理分块。我钦定一个块只包含簇路径上的点权，从某个关键点出发，不包括它在虚树上的父亲。预处理每个块的点权和、块中点数。为了方便的知道一个点属于哪个树簇，我们在上界点的子节点标记下界点的位置。

树分块后大概长这个样子。其中圆表示关键点，加粗的为关键点到关建点之间的路径，即簇路径。四个不同颜色的路径表示下面会遇到的四种不同类型的查询，画圈的点为路径的 LCA。

我们可以把查询（修改）\(x \to y\) 拆成 \(x \to LCA(x,y)\) 和 \(y \to LCA(x,y)\) 两段，并特殊处理 \(LCA(x,y)\)。

先考虑如何利用树分块求 LCA。

大致有如上图所示的四种情况。

• 当两点属于不同的树簇；
  • 当两个树簇的下界点在虚树上不构成祖孙关系，如红色路径所示。则两点在虚树上的祖先就是两个点的 LCA；
  • 当两个树簇的下界点在虚树上构成祖孙关系，如绿色路径所示。则 LCA 为所在树簇下界点较浅的点到簇路径上最近点。
• 当两点属于同一树簇，暴力往上跳到上界点并打标记即可求 LCA。如蓝色和橙色路径所示。

由虚树大小为 \(O(\sqrt n)\)，向上期望距离也为 \(O(\sqrt n)\)，求 LCA 的复杂度为 \(O(\sqrt n)\)。

然后处理的是 \(x \to l\) 的查询（修改）（其中 \(l\) 为 \(x\) 祖先），为了方便，我令这样的查询（修改）包括 \(x\) 而不包括 \(l\)。像序列分块一样对 \(x\) 和 \(l\) 所在树簇暴力，其他的树簇打懒标即可。

由于代码很长，这里只放部分。完整代码见 LOJ 上的提交记录。

部分代码

u32 ww[N],__pre[N];//pre 数组只需要 23 位，将高位当 bool 数组用
#define pre(x) (__pre[x]&(0xffffff))
#define vis(x) (__pre[x]>>31)
#define onvt(x) ((__pre[x]>>30)&1) //是否在虚树上
#define onmain(x) ((__pre[x]>>29)&1)  //是否在簇分支上
void fstbuild(u32 x){//第一次初始化分块
    id[x]=++tcnt;
    uid[tcnt]=x;
    if(x==1) return;
    u32 d=id[x],p=pre(x);
    sum[d]=ww[x],dis[d]=1,tag[d]=0;
    while(!onvt(p)){
        dis[d]++,sum[d]+=ww[p];
        if(onvt(pre(p))) clu[p]=x;//标记 cluster 的下界点
        p=pre(p);
    }
    fa[d]=id[p];
    dep[d]=dep[fa[d]]+1;
}
void rebuild(u32 x){//暴力重建分块
    if(x==1) return;
    u32 d=id[x],p=pre(x);
    sum[d]=ww[x]+dis[d]*tag[d],dis[d]=1;
    while(!onvt(p))
        dis[d]++,sum[d]+=ww[p],p=pre(p);
}
u32 get_clu(u32 p){//返回所在 cluster 的下界点
    if(p==1) return 1;
    u32 x=p;
    while(!clu.count(x)&&!onvt(x)) x=pre(x);
    if(onvt(x)) return x;
    return clu[x];
}
u32 get_to_main(u32 p){//从一个点跳到最近的簇路径上的点
    if(p==1) return 1;
    while(!onmain(p)) p=pre(p);
    return p;
}
void build(){//建虚树
    tmp.push_back(1);
    __pre[1]|=(1u<<30);
    for(u32 i=0;i<min(n,B);i++){//随机撒点
        u32 p=uniform_int_distribution<u32>(1,n)(rnd);
        tmp.push_back(p);
        __pre[p]|=(1u<<30);
    }
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(u32 i=0;i<tmp.size();i++){
        u32 p=tmp[i];
        while(p){
            if(onmain(p)){
                if(!onvt(p)){
                    tmp.push_back(p);
                    __pre[tmp[i]]|=(1u<<30);
                }
                break;
            }
            __pre[p]|=(1u<<29);
            p=pre(p);
        }
    }
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(u32 i=0;i<tmp.size();i++){
        fstbuild(tmp[i]);
    }
}
u32 slca(u32 x,u32 y){//求虚树上的 LCA
    while(x!=y){
        if(dep[x]<dep[y]) x^=y^=x^=y;
        x=fa[x];
    }
    return x;
}
u32 lca(u32 x,u32 y){
    u32 a=get_clu(x),b=get_clu(y);
    if(a!=b){
        u32 w=uid[slca(id[a],id[b])];
        if(w!=a&&w!=b) return w;//情况一
        if(w==b) a^=b^=a^=b,x^=y^=x^=y;
        return get_to_main(x);//情况二
    }else{//情况三
        u32 ff=uid[fa[id[a]]];
        for(u32 p=x;p!=ff;p=pre(p))
            __pre[p]|=1u<<31;
        b=ff;
        for(u32 p=y;p!=ff;p=pre(p))
            if(vis(p)){b=p;break;}
        for(u32 p=x;p!=ff;p=pre(p))
            __pre[p]&=~(1u<<31);
        return b;
    }
}
u32 qry_link(u32 f,u32 x){//f 为 x 的祖先，x（含）->f（不含） 的链求和
    u32 w=get_clu(f),g=get_clu(x);
    unsigned res=0;
    if(w==g){//特殊情况，两点在同一 cluster，暴力
        for(u32 p=x;p!=f;p=pre(p))
            res+=ww[p]+onmain(p)*tag[id[w]];//我采用标记永久化
        return res;
    }
    if(w!=f){
        for(u32 p=w;p!=f;p=pre(p)) res+=ww[p]+onmain(p)*tag[id[w]];
        f=w;
    }
    u32 ff=uid[fa[id[g]]];
    if(ff!=x){
        for(u32 p=x;p!=ff;p=pre(p)) res+=ww[p]+onmain(p)*tag[id[g]];
        x=ff;
    }
    x=id[x],f=id[f];
    for(u32 p=x;p!=f;p=fa[p]) res+=sum[p];
    return res;
}
u32 qry(u32 x,u32 y){
    u32 l=lca(x,y);
    u32 res=0;
    res+=qry_link(l,x);
    res+=qry_link(l,y);
    res+=ww[l];
    if(onmain(l)) res+=tag[id[get_clu(l)]];
    return res;
}
//修改类似的，不放了。