原文链接https://www.cnblogs.com/zhouzhendong/p/CF1053C.html
题意
有 $n$ 个物品，第 $i$ 个物品在位置 $a_i$ ，重量为 $w_i$ 。使得重量为 $x$ 的物品移动一单位距离的花费是 $x$ 。接下来 $q$ 个操作，有两种类型：
1. 将物品 $i$ 的重量修改成 $nw$ 。
2. 询问把区间 $[L,R]$ 内的物品都移动到一段连续的区间 $[x,x+R-L]$ 内，并且互不重叠，相对顺序保持不变，问最小花费。
保证 $a_i$ 递增。
$n,q\leq 2\times 10^5, 1\leq a_i,w_i\leq 10^9$
题解
比赛的时候，很快想到了解决这个问题的前几步：
$a[i]-=i$
然后就变成了所有物品都移动到一个点的问题了。直接求带权中位数就好了。
然后我“成功”地把问题转化成了下面这个问题：
"求区间带权中位数，单点修改。"
哎呀这个区间中位数还得树套树啊，得统计区间小于等于某一个数的答案还得单点修改啊！
于是我花了20分钟想出了一个非常复杂的树套树 log^2 做法。于是码呀码，码到最后15分钟码完了，根本调不出来。
赛后膜了一发 App ，我仍然一脸懵逼。
直到最后躺在床上的时候，突然我明白了。
我忽略了什么呢？
位置是单调不减的！！！
所以要什么树套树啊。
言归正传。
考虑求区间中位数。直接二分就好了，用树状数组快速计算区间权值和。
考虑得到的位置为 $p$ ，那么，$ans=\sum_{i\in[L,R]} w_i|a_i-p|$ ，再用个树状数组维护一下区间 $w_ia_i$ 的和，最后求答案的时候分两段算就好了。
我***************连这种玩意儿都没做出来，我好菜啊……
说着就伤心，我也知道这个题解质量不好，但是我很伤心，就不改了吧。
时间复杂度 $O(n \log n + q \log^2 n)$ 。
代码
#includeusing namespace std;typedef long long LL;const int N=200005,mod=1e9+7;LL read(){ LL x=0,f=1; char ch=getchar(); while (!isdigit(ch)&&ch!='-') ch=getchar(); if (ch=='-') f=-1,ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-48,ch=getchar(); return x*f;}int n,Q;int a[N],w[N];LL c1[N];int c2[N];void add(int &x,int y){if ((x+=y)>=mod)x-=mod;}void add1(int x,LL d){for (;x<=n;x+=x&-x)c1[x]+=d;}void add2(int x,int d){for (;x<=n;x+=x&-x)add(c2[x],d);}LL ask1(int x){LL ans=0;for (;x;x-=x&-x)ans+=c1[x];return ans;}int ask2(int x){int ans=0;for (;x;x-=x&-x)add(ans,c2[x]);return ans;}void opt1(int i,int nw){ add1(i,-w[i]); add2(i,(-1LL*w[i]*a[i]%mod+mod)%mod); w[i]=nw; add1(i,w[i]); add2(i,1LL*w[i]*a[i]%mod);}void opt2(int L,int R){ LL t=ask1(L-1); LL sum=ask1(R)-t; int le=L,ri=R,mid,ans=R; while (le<=ri){ mid=(le+ri)>>1; LL v=ask1(mid)-t; if (v*2>=sum) ri=mid-1,ans=mid; else le=mid+1; } LL v11=ask2(ans)-ask2(L-1),v12=-1LL*a[ans]*((ask1(ans)-t)%mod)%mod; LL v21=ask2(R)-ask2(ans),v22=-1LL*a[ans]*((ask1(R)-ask1(ans))%mod)%mod; LL Ans=(v21+v22-v11-v12)%mod; Ans=(Ans+mod)%mod; printf("%I64d\n",Ans);}int main(){ n=read(),Q=read(); for (int i=1;i<=n;i++) a[i]=read()-i+n; memset(c1,0,sizeof c1); memset(c2,0,sizeof c2); for (int i=1;i<=n;i++){ w[i]=read(); add1(i,w[i]); add2(i,1LL*w[i]*a[i]%mod); } while (Q--){ int x=read(),y=read(); if (x<0) opt1(-x,y); else opt2(x,y); } return 0;}