[USACO25JAN] Median Heap G 题解

· · 题解

金组签到题。

定义修改操作为将某个结点的值修改为另一个值的操作，定义替换操作为将某个结点的值替换为它与两个儿子的值的中位数的操作。

考虑暴力：对于每个询问 m，暴力地从下往上做树形 DP，假设当前考虑到结点 u 且 u 有两个儿子；令 f_{u,0/1/2} 分别表示使结点 u 上执行替换操作后的值小于 / 等于 / 大于 m 的最小花费，w_{u,0/1/2} 分别表示使结点 u 上执行修改操作后、执行替换操作前的值小于 / 等于 / 大于 m 的最小花费，u 的两个儿子为 k_1,k_2，则有转移：

f_{u,i}=\min\limits_{\operatorname{med}(x,y,z)=i}f_{k_1,x}+f_{k_2,y}+w_{u,z}

其中 \operatorname{med}(x,y,z) 表示 x,y,z 的中位数。w 的值直接考虑结点的初始值是否需要被修改即可。对于 u 没有儿子的情况，则 f_u\gets w。

观察到可以离线所有询问：将询问 m 从小到大排序，w_{u,0/1/2} 的值至多被修改 2 次（小于变为等于，等于变为大于），而每次修改只会影响到 u 以及 u 的祖先，而完全二叉树的树高是 O(\log n) 级别的，所以暴力往上跳父亲进行修改即可。时间复杂度 O(n\log n+q\log q)

赛时代码，常数较大。放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int median(int x,int y,int z){
  return x+y+z-max({x,y,z})-min({x,y,z});
} // 求三个数的中位数
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,l1=0,l2=0; cin>>n;
  vector<int> a(n+1),c(n+1);
  for(int i=1;i<=n;i++)
    cin>>a[i]>>c[i];
  vector<int> ps(n);
  iota(ps.begin(),ps.end(),1);
  sort(ps.begin(),ps.end(),[&](int x,int y){
    return a[x]<a[y];
  }); // 将结点按权值排序，方便找到需要修改的结点
  vector f(n+1,vector<ll>(3,1e18));
  int q; cin>>q;
  auto upd=[&](int u,int m){
    f[u]=vector<ll>(3,1e18);
    vector<ll> w(3);
    if(a[u]<m)w[1]=w[2]=c[u];
    else if(a[u]==m)w[0]=w[2]=c[u];
    else w[0]=w[1]=c[u];
    // 预处理修改花费 w
    if((u<<1|1)<=n){
      for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
          for(int k=0;k<3;k++){
            int m=median(i,j,k);
            f[u][m]=min(f[u][m],f[u<<1][i]+f[u<<1|1][j]+w[k]);
          } // 暴力枚举三个结点的值
    } // 有儿子
    else f[u]=w; // 没有儿子
  };
  auto g=[&](int x,int m){
    for(int i=0;x>>i;i++)
      upd(x>>i,m);
  }; // 暴力跳祖先进行更新
  vector<pii> Q(q);
  for(int i=0;i<q;i++)
    cin>>Q[i].first,Q[i].second=i;
  vector<ll> R(q);
  sort(Q.begin(),Q.end());
  for(int i=n;i;i--)
    g(i,0);
  for(auto [m,p]:Q){
    while(l1<n&&a[ps[l1]]<m)g(ps[l1++],m);
    while(l2<n&&a[ps[l2]]<=m)g(ps[l2++],m);
    R[p]=f[1][1];
  } // 离线下来扫描
  for(ll i:R)cout<<i<<'\n';
  return 0;
}