原文链接https://www.cnblogs.com/zhouzhendong/p/CF1053C.html
题目传送门 - CF1053C
题意
有 $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)$ 。
代码
#include <bits/stdc++.h>
using 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;
}