CF1030F题解

Xttttr / 2023-08-09 / 原文

CF1030F 题解

传送门更好的阅读体验

简化题意：有 $n$ 个小球，每个小球在位置 $a_i$，移动一格的代价是 $w_i$，有两种操作，一种是将 $w_x$ 改成 $y$，一种是查询 $\min\limits_{x=1}^n\{\sum\limits_{i=l}^rw_i\times (|a_x-a_i|+|x-i|)\}$。

思路

很好的线段树二分练手题。

对于每个询问，首先肯定要找到使得答案最小的 $x$。我们考虑当前的 $x$ 变成 $x+1$ 时答案的改变量，发现就是 $(a_{x+1}-a_x)\times(\sum\limits_{i=l}^xw_i-\sum\limits_{i=x+1}^rw_i)$，因此 $x$ 取到 $[l,r]$ 的带权中位数时最优，即最小的满足 $\sum\limits_{i=l}^x w_i\geqslant\sum\limits_{i=x+1}^rw_i$ 的 $x$。

于是就可以直接二分+线段树来找这个 $x$，这也是其他题解的做法，单次复杂度是 $O(\log^2n)$ 的。如果直接用线段树二分的话就是 $O(\log n)$ 的，感觉还是比较板的。

接下来计算答案比较简单，就不再赘述了。

贴一下线段树二分的代码。

struct Seg{
    ll t[N<<2];
    inline void upd(int rt){t[rt]=t[ls]+t[rs];}
    inline void modify(int rt,int l,int r,int x,int k){
        if(l==r){
            t[rt]=k;
            return;
        }
        if(x<=mid)modify(ls,l,mid,x,k);
        else modify(rs,mid+1,r,x,k);
        upd(rt);
    }
    inline ll query(int rt,int l,int r,int L,int R){
        if(L>R)return 0;
        if(L<=l&&r<=R)return t[rt];
        ll ans=0;
        if(L<=mid)ans=query(ls,l,mid,L,R);
        if(mid<R)ans+=query(rs,mid+1,r,L,R);
        return ans;
    }
    inline int query(int rt,int l,int r,int L,int R,ll sum,ll &cur){
        if(l==r){
            if(2ll*(t[rt]+cur)<sum){
                cur+=t[rt];
                return -1;
            }
            return l;
        }
        if(L<=l&&r<=R){
            if(2ll*(t[rt]+cur)<sum){
                cur+=t[rt];
                return -1;
            }
            if(2ll*(t[ls]+cur)>=sum)return query(ls,l,mid,L,R,sum,cur);
            cur+=t[ls];
            return query(rs,mid+1,r,L,R,sum,cur);
        }
        int ans=-1;
        if(L<=mid)ans=query(ls,l,mid,L,R,sum,cur);
        if(~ans)return ans;
        return query(rs,mid+1,r,L,R,sum,cur);
    }
}T;