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;