题目概述

有 $n$ 个物品，第 $i$ 个物品在 $a_i$ ，移动一格需要 $w_i$ 的代价。现在有两种操作：1.把 $w_x$ 变成 $y$ 。2.询问把 $[L,R]$ 的物品移动到 $[x,x+R-L]$ （ $x$ 自定）需要的最小代价，移动的时候不能穿过其他物品。

解题报告

答案式子长这样：$\sum_{i=L}^{R}w_i|x+i-L-a_i|$ ，可以发现当 $x$ 向后移动 $1$ 的时候，小于等于 $x$ 的全部加了 $w_i$ ，而大于 $x$ 的全部减了 $w_i$ 。所以答案随着 $x$ 增大先下降后上升，并且除了最小值之外不会有相同的一段，证明的话考虑 $x$ 和 $x+1$ 的斜率，肯定是不降的（越往后只会有越来越多的变成正数）。

也就是说贡献是一个单谷函数，我们直接二分或者三分找谷底就好了，计算贡献的时候可以再二分一次去掉绝对值，然后用树状数组统计一下。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=200000,MOD=1e9+7;

int n,te,a[maxn+5],w[maxn+5];LL sum[maxn+5];int val[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Update(int x,int y){
    for (int i=x;i<=n;i+=i&-i) sum[i]-=w[x];
    for (int i=x;i<=n;i+=i&-i) AMOD(val[i],MOD-(LL)w[x]*(MOD+x-a[x])%MOD);
    w[x]=y;for (int i=x;i<=n;i+=i&-i) sum[i]+=y;
    for (int i=x;i<=n;i+=i&-i) AMOD(val[i],(LL)y*(MOD+x-a[x])%MOD);
}
inline LL Sum(int x) {LL S=0;for (int i=x;i;i-=i&-i) S+=sum[i];return S;}
inline int Val(int x) {int V=0;for (int i=x;i;i-=i&-i) AMOD(V,val[i]);return V;}
inline bool check(int x,int y,int p){
    int L=x,R=y;for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) a[mid]<=p+mid-x?L=mid+1:R=mid-1;
    return Sum(R)-Sum(x-1)-(Sum(y)-Sum(R))>0;
}
inline int getans(int x,int y,int p){
    int L=x,R=y;for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) a[mid]<=p+mid-x?L=mid+1:R=mid-1;
    int ans=0;AMOD(ans,(Sum(R)-Sum(x-1))%MOD*(MOD+(p-x)%MOD)%MOD);AMOD(ans,Val(R));AMOD(ans,MOD-Val(x-1));
    AMOD(ans,MOD-(Sum(y)-Sum(R))%MOD*(MOD+(p-x)%MOD)%MOD);AMOD(ans,MOD-Val(y));AMOD(ans,Val(R));return ans;
}
int main(){
    freopen("F.in","r",stdin);freopen("F.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1,x;i<=n;i++) scanf("%d",&x),Update(i,x);
    for (int x,y;te;te--)
        if ((scanf("%d%d",&x,&y),x)<0) Update(-x,y); else{
            int L=-(1e9),R=1e9;for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(x,y,mid)?R=mid-1:L=mid+1;
            printf("%d\n",getans(x,y,L));
        }return 0;
}