题解：P11673 [USACO25JAN] Median Heap G

· · 题解

dp 题。

首先先把 a 和 m 离散化，变成 [1,n+q] 之间的数。

现在来分析这一“近似中位数”的特性：不妨设当前节点为 x，p_i 表示 i 的子树操作完后，i 这个节点上的值是多少。那么 p_x = y 的充要条件是 a'_x（替换操作进行完之后的 a_x 值，与原来的 a_x　做区分），p_{2x}，p_{2x+1} 中，恰好有一个小于等于 y，一个等于 y，一个大于等于 y。

此时，就能自然而然地设出一个 dp 的状态：设 dp_{i,j} 表示希望令 p_i = j，至少需要在子树内支付多少代价。但是我们发现直接这样设好像无法转移，还需要两个辅助数组： dp1_{i,j} 表示希望令 p_i \leq j　的最小代价，dp2_{i,j} 表示希望令 j \leq p_i 的最小代价。转移方程比较繁琐，但不难推导（具体见文末的代码的 push_down 函数 ）。

就这样，我们有了一个 O(n^2) 的做法。但是这样只能拿到 7 个测试点的分数，显然不够。

然而，如果考虑 j 的值从 y 变成 y+1，会发现实际上 dp 值变化的点很少。对于所有 x | a_x = y-1 以及 x| a_x = y 的 x，只有 x 以及他到根的节点的值可能会变！由于这些数加起来一共只有 O(n) 个，所以在 j 从 1 一直移动到 n+q 的过程中总共只需要改变 n \log n 个位置的 dp 值。

所以我们可以添加一个优化，只在 dp_{x,j} 中更改 a_x = j 或 a_x = j+1 的 x 到根的路径上的节点的 dp 值，从而得到 dp_{x,j+1}，经过优化后的复杂度为 O((n+q) \log n)。不明白为什么开 4 秒……

int n,q;
const int MAXN=2e6+5;
int a[MAXN],c[MAXN];
int p[MAXN],l,now;
int d[MAXN]; 
vector<int>que[MAXN],poi[MAXN];
ll tox[MAXN],toe[MAXN],tod[MAXN];//tox：文中的 dp1，toe：文中的 dp，tod：文中的 dp2
void push_up(int x){//转移方程
    tox[x]=min({tox[x<<1]+(a[x]>now)*c[x],tox[x<<1|1]+(a[x]>now)*c[x],tox[x<<1]+tox[x<<1|1]});
    tod[x]=min({tod[x<<1]+(a[x]<now)*c[x],tod[x<<1|1]+(a[x]<now)*c[x],tod[x<<1]+tod[x<<1|1]});
    toe[x]=min({min(tox[x<<1]+tod[x<<1|1],tod[x<<1]+tox[x<<1|1])+(a[x]!=now)*c[x],
    toe[x<<1]+min((a[x]>now)*c[x]+tod[x<<1|1],(a[x]<now)*c[x]+tox[x<<1|1]),
    toe[x<<1|1]+min((a[x]>now)*c[x]+tod[x<<1],(a[x]<now)*c[x]+tox[x<<1])});
}
ll ans[MAXN];
void dfs(int x){
    if(x>n){
        toe[x]=1e18;
        return ;
    }
    if((x<<1)>n){
        toe[x]=(a[x]!=now)*c[x];
        tod[x]=(a[x]<now)*c[x];
        tox[x]=(a[x]>now)*c[x];
    }else{

        dfs(x<<1);dfs(x<<1|1);
        push_up(x);
    }
//  printf("%d  %d %d %lld %lld %lld\n",x,a[x],c[x],tod[x],tox[x],toe[x]);
}
void pus(int x){
    if(!x)return ;
    if(x*2>n){
        toe[x]=(a[x]!=now)*c[x];
        tod[x]=(a[x]<now)*c[x];
        tox[x]=(a[x]>now)*c[x];

    }else{
        push_up(x);
    }

    pus(x>>1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&c[i]);
        p[++l]=a[i];
    }scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d",&d[i]);p[++l]=d[i];
    }

  //离散化
    sort(p+1,p+1+l);
    l=unique(p+1,p+1+l)-p-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(p+1,p+1+l,a[i])-p;
        poi[a[i]].push_back(i);
    }
    for(int i=1;i<=q;i++){
        d[i]=lower_bound(p+1,p+1+l,d[i])-p;
        que[d[i]].push_back(i);
    }

    dfs(1);
//  now=4;
//  dfs(1);

    for(int i=1;i<=l;i++){
        now=i;
//      dfs(1);

        for(int j=0;j<poi[i-1].size();j++){
            pus(poi[i-1][j]);
        }
        for(int j=0;j<poi[i].size();j++){
            pus(poi[i][j]);
        }
        for(int j=0;j<que[i].size();j++){
            ans[que[i][j]]=toe[1];
        }
    //  printf("now=%d:\n",i);
    //  for(int j=1;j<=n;j++){
    //      printf("%d %d %d %lld %lld %lld\n",j,a[j],c[j],tox[j],toe[j],tod[j]);
    //  }
    }
    for(int i=1;i<=q;i++){
        printf("%lld\n",ans[i]);
    }
}