XXI Open Cup GP of Xiaomi M

对原树进行轻重链剖分；

假设当前在处理以 $w$ 为根的大小为 $n$ 的子树，且 $w$ 是重链头，当前莫队状态为 $w$ 的子树补。可以在 $O(n)$ 时间扫出 $w$ 所在重链上，每个结点的子树补（这部分总代价为$O(n \log n)$）；

然后将w所在重链的每个点的轻儿子找出来，之后要递归处理；

将这些轻儿子按子树大小加权，以及重链上每个点按 $1$ 加权，建哈夫曼树，在哈夫曼树上dfs，维护哈夫曼树上当前点的子树补，到达叶子时若叶子对应轻儿子则递归处理轻子树。将整个递归过程中，产生的哈夫曼树拼接起来，得到所有叶子权为 $1$ 的哈夫曼树，由于哈夫曼树上，每向下两层子树权值和至少减小一个常数比例，由此得到遍历哈夫曼树过程的莫队的复杂度是 $O(n\log n)$ 的。

因此总时间 $O(n\log n)$。

使用轻重链剖分

对根所在重链，可以在n次插入得到重链上每个点的答案，
轻子树需要建立哈夫曼树，叶子的权重为子树规模，重链也作为一个叶子，权重为重链长度；

在哈夫曼树上dfs，维护当前子树外对应的集合，移动到叶子时就递归到了轻子树上的子问题，所需插入次数为所有非叶结点的子树规模之和（子树规模为子树中叶结点的权重之和）；

#include<bits/stdc++.h>
const int maxn=1e5,N=maxn+7,inf=1e9+7;
std::mt19937 mt(time(0));//
int read(int L,int R){
    //return L+mt()%(R-L+1);//
    int x;
    assert(scanf("%d",&x)==1);
    assert(L<=x);
    assert(x<=R);
    return x;
}
int fa[N],in[N],q[N],ql,qr,son[N],sz[N],n,m,ch[N*2][2],cp;
std::vector<int> e[N];
void hld(){
    for(int i=1;i<=n;++i)in[i]=0,sz[i]=1,son[i]=0;
    for(int i=1;i<=n;++i)++in[fa[i]];
    ql=qr=0;
    for(int i=1;i<=n;++i)if(!in[i])q[++qr]=i;
    while(ql!=qr){
        int w=q[++ql],f=fa[w];
        if(!f)continue;
        if(!--in[f])q[++qr]=f;
        sz[f]+=sz[w];
        if(sz[w]>sz[son[f]])son[f]=w;
    }
    //for(int i=1;i<=n;++i)printf("%d:%d\n",i,son[i]);
    ql=qr=0;
    cp=n;
}
int ins_cnt=0,undo_cnt=0,pos;
char otpt[8*5500000+1000000];
int temp[10];
void out(int u){
    //if( u > 100000 ) std :: cerr << u << std :: endl;
    static int *q=temp;
    if(!u) otpt[pos++]='0';
    else
    {
        while(u)
        {
            int b=u/10;
            *q++=u-b*10+'0';
            u=b;
        }
        while(q!=temp)
            otpt[pos++]=*--q;
    }
}
void chk(int w){
    //printf("%d: ",w);
    //for(int i=1;i<=qr;++i)printf("(%d)",q[i]);puts("");
    otpt[pos++]='=';
    out(w);
    assert(qr==n-sz[w]);
}
void ins(int w){
    //printf("+%d\n",w);
    ++ins_cnt;
    otpt[pos++]='+';
    out(w);
    q[++qr]=w;
}
void undo(int q0){
    //printf("-%d\n",q0);
    while(qr!=q0)
    {
        qr--;
        otpt[pos++]='-';
    }
    ++undo_cnt;
    ql=qr;
}
struct Pos{
    int x,sz;
    bool operator<(const Pos&w)const{return sz<w.sz;}
}ps1[N],ps2[N];
int pp1,pp2;
struct Undo{
    int l;
    Undo():l(qr){}
    ~Undo(){undo(l);}
};
void bfs(){
    while(ql!=qr){
        int v=q[++ql];
        for(int x:e[v])ins(x);
    }
}
void dfs(int w);
void dfs3(int w){
    //printf("dfs3 %d\n",w);
    if(w<=n)return ins(w);
    dfs3(ch[w][0]);
    dfs3(ch[w][1]);
}
void dfs2(int w,int u=0){
    //printf("dfs2 %d(%d %d) %d\n",w,ch[w][0],ch[w][1],u);
    Undo _;
    if(u){
        ql=qr;
        dfs3(u);
        bfs();
    }
    if(w<=n)return dfs(w);
    int lc=ch[w][0],rc=ch[w][1];
    dfs2(lc,rc);
    dfs2(rc,lc);
}
void dfs(int w){
    pp1=pp2=0;
    {
        Undo _;
        for(int u=w;u;){
            chk(u);
            int nx=son[u];
            ins(u);
            ql=qr;
            for(int x:e[u])if(x!=nx){
                ins(x);
                ps1[pp1++]=Pos{x,sz[x]};
            }
            bfs();
            u=nx;
        }
    }
    if(!pp1)return;
    std::sort(ps1,ps1+pp1);
    ps1[pp1].sz=inf;
    ps2[pp2].sz=inf;
    int cnt=pp1,p1=0,p2=0;
    for(;;){
        Pos a=(ps1[p1]<ps2[p2]?ps1[p1++]:ps2[p2++]);
        if(!--cnt){
            Undo _;
            for(int u=w;u;u=son[u])ins(u);
            return dfs2(a.x);
        }
        Pos b=(ps1[p1]<ps2[p2]?ps1[p1++]:ps2[p2++]);
        ps2[pp2++]=Pos{++cp,a.sz+b.sz};
        ps2[pp2].sz=inf;
        ch[cp][0]=a.x;
        ch[cp][1]=b.x;
    }
}
int main(){
    //freopen( "data1.in" , "r" , stdin );
    //freopen( "data1.out" , "w" , stdout );
    n=read(1,maxn);
    //n=10;
    for(int i=2;i<=n;++i){
        int f=fa[i]=read(1,i-1);
        //printf("%d\n",f);
        e[f].push_back(i);
    }
    hld();
    dfs(1);
    //fprintf(stderr,"%d %g %g\n",n,ins_cnt*1./(n*log2(n)),undo_cnt*1./n);
    otpt[pos++]='!';
    fwrite( otpt , 1 , pos , stdout );
    return 0;
}

EditorialBot 的網誌

網誌

評論

發表評論