题解 P7124 【[Ynoi2008] stcm】

· · 题解

给出一个分治做法。

\texttt{Solution}

在 dfn 序上考虑，点 x 的子树补形如整个区间扣掉 [dfn_x,dfn_x+siz_x-1]，考虑直接分治。

一个分治区间 [l,r]，处理所有 [dfn_x,dfn_x+siz_x-1] 完全包含于 [l,r] 的询问，且已经加入了 [1,l-1],[r+1,n] 的全部信息。

考虑每一层分治处理完所有跨过区间中点 mid 的询问：由于子树区间只有包含关系，所有越过 mid 的区间存在偏序关系，我们增量加入信息即可。

未跨过 mid 的询问直接向下递归。

对于分治的每一层，显然处理跨过区间中点 mid 的询问时进行的加入信息操作为 O(n)，则总加入次数为 O(n\log n)。

给出核心代码：

void solve(vec p,int l,int r,int d){
    if(!p.size())return ;
    if(l==r){printf("=%d",rdfn[l]);return ;}
    int mid=l+((r-l)>>1);
    vec lt,rt;lt.clear();rt.clear();
    int lp=l-1,rp=r+1;
    for(auto x:p){
        if(R[x]<=mid)lt.eb(x);
        else if(x>mid)rt.eb(x);
        else{
            while(lp<x-1)trans(rdfn[++lp]);
            while(rp>R[x]+1)trans(rdfn[--rp]);
            printf("=%d",rdfn[x]);
        }
    }
    for(int i=lp;i>=l;i--)printf("-");
    for(int i=rp;i<=r;i++)printf("-");
    for(int i=mid+1;i<=r;i++)trans(rdfn[i]);
    solve(lt,l,mid,d+1);
    for(int i=mid+1;i<=r;i++)printf("-");
    for(int i=l;i<=mid;i++)trans(rdfn[i]);
    solve(rt,mid+1,r,d+1);
    for(int i=l;i<=mid;i++)printf("-");
    return ;
}