储物点的距离

题意:给定i和i+1两点的距离,i点的货物数量,以及费用计算方法ans=x * dist( i , j ),dist(i,j)为两点间距离
然后每次查询将区间(i,j)的货物全部转移到x点所需要的费用ans
题解:前缀和
(1)求1点到i点的距离前缀和a[]
区间[1,i]点货物集中到1点,1点货物总和的前缀和b[]
区间[1,i]点货物集中到1点,所需要的价值的前缀和c[]
(2)分情况讨论
区间[L,R],点X
如果X小于等于L,那么可以先把区间[L,R]所有的货物集中到1点的花费为c[R]-c[L],但是对于对于每个j点,j在[L,R],都多走了a[x],所以要减去(b[R]-b[L])*a[x]
如果X大于等于R,那么可以先让b[R]-b[L]数量的货物从a[1]走到a[x],但是对于每个j点,j在[L,R]之间都多走了a[j],算下来总共多走了c[R]-c[L]
如果X在L和R之间,那么按照上述式子先求解,把L当作R情况,即求解[L,X]
然后求[X,R]相当于上面两种情况结合
时间复杂度:O(n)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,p=1e9+7;
int n,m,a[N],w[N],s[N];
signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for(int i=2;i<=n;i++)    cin>>a[i],a[i]=(a[i]+a[i-1])%p;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        s[i]=(a[i]*w[i]%p+s[i-1]+s[i])%p;
        w[i]=(w[i]+w[i-1])%p;
    }
    while(m--){
        static int x,l,r,res;   cin>>x>>l>>r;
        if(x<=l){
            res=(s[r]-s[l-1]+p)%p; res=(res-(w[r]-w[l-1]+p)%p*a[x]%p+p)%p;
        }else if(x>=r){
            res=((w[r]-w[l-1]+p)%p*a[x]%p-(s[r]-s[l-1]+p)%p+p)%p;
        }else{
            res=(s[r]-s[x-1]+p)%p; res=(res-(w[r]-w[x-1]+p)%p*a[x]%p+p)%p;
            res=(res+(w[x]-w[l-1]+p)%p*a[x]%p-(s[x]-s[l-1]+p)%p)%p;
        }
        res=(res+p)%p;
        cout<<res<<'\n';
    }
    return 0;
}