Top Cluster分块 & 莫队二次离线

tzl_Dedicatus545 · 2024-12-20 22:57:19 · 算法·理论

你确定不是 top cluster？｜审核管理员：MatrixGroup

我也不知道为什么要把这两个放到一起写。

Top Cluster

Top Cluster 会将树划分为满足一下性质的若干个簇：

• 每个簇的大小是 O(B) 的。
• 不同簇的边界不交
• 每个簇至多有两个点与外界有交，我们称之为界点
• 所有界点构成一棵树，叫做原树的收缩树

偷张图：

算法流程：

对原树进行 dfs，同时维护当前点 u 的每个子树 v 中待匹配点的个数。

我们会让当前节点 u 成为待匹配的界点当且仅当：

• 当前待匹配点个数 >B

之后，我们贪心的确定若干以 u 为上界点的簇。

// bn 是待匹配界点，wat 是待匹配点
void par(int u){
    ctp[u]=tp;wat[u]=1;
    int cc=0;
    for(auto [v,w]:adj[u])  if(v!=fa[u]){
        st[++tp]=v;par(v);
        wat[u]+=wat[v];
        if(bn[v]){
            bn[u]=bn[v];cc++;
        }
    }
    if(wat[u]>B || cc>1 || u==1){                  //判断
        wat[u]=0;bn[u]=u;adj[u].pb({0,0});
        int cwat=0,cd=0,j=ctp[u]+1;
        ctp[0]=inf;
        for(auto [v,_]:adj[u])  if(v!=fa[u] || !fa[u]){
            if(cwat+wat[v]>B || (cd && bn[v]) || !v){           
                for(;j<=min(tp,ctp[v]-1);j++) cur[++ccc]=st[j];  //贪心进行匹配
                add_cl(u,cd);
                cwat=cd=0;
            }
            cwat+=wat[v];
            if(bn[v])   cd=bn[v];
        }
        adj[u].pop_back();
        tp=ctp[u];
    }
}

加入一个簇的过程是简单的：

void add_cl(int u,int v){
    if(v){
        FA[v]=u;key.pb(v);
        near[u]=u;
        for(int t=v;t!=u;t=fa[t])   near[t]=t;
    }
    cclu++;
    rep(i,1,ccc,1){
        int r=cur[i];clu[cclu].pb(r);cid[r]=cclu;down[r]=v;up[r]=u;
        if(!v){near[r]=u;continue ;}
        int w=0;for(w=r;!near[w];w=fa[w]);
        near[r]=near[w];
    }
    if(v)   up[v]=v;
    ccc=0;
}

tdnmo

考虑对树做 Top-Cluster 分块。

若一个询问点不在收缩树上，或者它没有下界点，则根据簇的性质，我们知道，这个点的有向邻域大小一定不超过 B，我们直接从 N(1,0) 移动过去即可。

否则，我们考虑将询问挂到它所在的下界点上，不妨设为 b，则我们每次先跳到 b 所在的邻域上，再跳回至 u。

从 b 的邻域跳到 u 至多产生 B 的代价（簇中点可能会重复计算），共有 \dfrac{n}{B} 个邻域，每个邻域一共产生 O(n) 的代价，取 B=\sqrt{n}， 既可以用 O(n\sqrt{n}) 的代价解决这个题。

莫队二次离线。

常规莫队中，我们每次移动 [l,r] 到 [l,r+1]，并计算贡献。

注意到我们每次移动端点都是一段区间：不妨设我们从 [l,r] 移动至 [l,R]。

如果贡献可差分，我们可以把它差分成这样：（不妨记 f(l,r,x) 为 [l,r] 对 x 产生的贡献）