题解：P11673 [USACO25JAN] Median Heap G

· · 题解

考虑一个暴力 dp，设 f_{u,j} 表示以 u 为根的子树，u 的数交换过后是 j 的最小代价，转移是 O(nV^2) 的。

发现上面的状态其实是冗余的，对于要求的数 m，其实只把所有数分为了三类 <m,=m,>m，因此，考虑以此重新设计状态优化，即 f_{u,0/1/2} 表示以 u 为根的子树，u 节点上的数 <m，=m，>m 枚举转移即可，单次查询复杂度 O(n)，总复杂度 O(nq)。

进一步地考虑优化，发现所有数最多只会有两次状态变换，换句话讲，假如每有一个点初值修改我们就跑一遍 dp，修改操作只会有 O(n) 个，而本题给定了是完全二叉树，因此树高只有 O(\log n)，考虑暴力修改，每次更新一个点初值，然后再更新其父亲，逐个向上，单次修改复杂度 O(\log n)，总复杂度 O(q+n\log n)。

具体实现可以将询问离线，排序后指针扫描逐个加点。

const ll N=1e6+5,M=2e4+5;
ll n,q,fa[N],f[N][3],b[N],c[N],ans[N],g[N][3],vis[N];
struct node{ll i,a,c;}a[N];
vector<pii> A;vector<ll> G[N];
inline ll med(ll x,ll y,ll z){ll mx=max({x,y,z});if(x==mx) return max(y,z);if(y==mx) return max(x,z);return max(x,y);}
inline void dfs(ll x,ll fa)
{
    f[x][2]=0,f[x][0]=f[x][1]=c[x];ll ls=0,rs=0;vis[x]=2;
    for(ll y:G[x]) if(y!=fa) dfs(y,x),ls?rs=y:ls=y;
    if(!ls||!rs) return;g[x][0]=g[x][1]=g[x][2]=inf;
    fo(0,i,2) fo(0,j,2) fo(0,k,2) ckmn(g[x][med(i,j,k)],f[ls][i]+f[x][j]+f[rs][k]);
    fo(0,i,2) f[x][i]=g[x][i];
}
inline void upd(ll x,ll k)
{
    if(!x) return;
    if(vis[x]==0) f[x][0]=0,f[x][1]=f[x][2]=c[x];
    if(vis[x]==1) f[x][1]=0,f[x][0]=f[x][2]=c[x];
    if(vis[x]==2) f[x][2]=0,f[x][0]=f[x][1]=c[x];
    ll ls=0,rs=0;for(ll y:G[x]) if(y!=fa[x]) ls?rs=y:ls=y;
    if(!ls||!rs) return upd(fa[x],2);g[x][0]=g[x][1]=g[x][2]=inf;
    fo(0,i,2) fo(0,j,2) fo(0,k,2) ckmn(g[x][med(i,j,k)],f[ls][i]+f[x][j]+f[rs][k]);
    fo(0,i,2) f[x][i]=g[x][i];
    upd(fa[x],2);
}
signed main(){
    // freopen("median.in","r",stdin);
    // freopen("median.out","w",stdout);
    read(n,q);fo(1,i,n) (i!=1?G[i/2].pb(i),G[i].pb(i/2):void()),fa[i]=i/2,read(a[i].a,a[i].c),c[i]=a[i].c,b[i]=a[i].c,a[i].i=i;
    sort(a+1,a+1+n,[&](node i,node j){return i.a<j.a;});ll x,y;
    fo(1,i,q) read(x),A.pb(mk(x,i));sort(all(A));
    ll i1=1,i2=1;dfs(1,0);
    for(auto [x,id]:A)
    {
        while(i2<=n&&a[i2].a<x) ++i2;
        while(i1<=n&&a[i1].a<x) vis[a[i1].i]=0,upd(a[i1].i,0),++i1;
        while(i2<=n&&a[i2].a==x) vis[a[i1].i]=1,upd(a[i2].i,1),++i2;
        // wr(x),pp,wr(id),pp,wr(i1),pp,wr(i2),pr;
        ans[id]=f[1][1];
    }
    fo(1,i,q) wr(ans[i]),pr;
    return 0;
}