题解 | #储物点的距离#

前缀和

根据题意可列出将区间[l,r]中所有货物运到x点的代价为 $\sum_{i=l}^{r}{b_{i}}*dist_{x,i},(1-1)$ ，其中， $dist_{x,i}$ 为x点到i点的距离；

不妨令储物点1为原点，定义 $a_{i}$ 为i点到1点的距离，显然 $a_{1}=0$ ；

此时(1-1)式可化为 $\sum_{i=l}^{r}{b_{i}}*\left| a_{x}-a_{i} \right|,(1-2)$ ，(1-2)式可分为以下三种情况：

1、x<=l，有 $\sum_{i=l}^{r}{b_{i}}*(a_{i}-a_{x})=\sum_{i=l}^{r}{a_{i}*b_{i}}-a_{x}*\sum_{i=l}^{r}{b_{i}}$ ；

2、x>=r，有 $\sum_{i=l}^{r}{b_{i}}*(a_{x}-a_{i})=a_{x}*\sum_{i=l}^{r}{b_{i}}-\sum_{i=l}^{r}{a_{i}*b_{i}}$ ；

3、l<x<r，有 $\sum_{i=l}^{r}{b_{i}}*\left| a_{x}-a_{i} \right|=\sum_{i=x+1}^{r}{b_{i}}*(a_{i}-a_{x})+\sum_{i=l}^{x}{b_{i}}*(a_{x}-a_{i})=\sum_{i=x+1}^{r}{a_{i}*b_{i}}-a_{x}*\sum_{i=x+1}^{r}{b_{i}}+a_{x}*\sum_{i=l}^{x}{b_{i}}-\sum_{i=l}^{x}{a_{i}*b_{i}}$

显然，只要维护三个前缀和数组即可，代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define N 200010
const ll am = 1e9+7;
ll a[N],b[N],c[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n-1;i++){    //维护一个距离前缀和数组
        ll temp;
        scanf("%lld",&temp);
        a[i+1] = (a[i]+temp%am)%am;
    }
    for(int j = 1;j <= n;j++){    
        ll temp1;
        scanf("%lld",&temp1);
        b[j] = temp1%am;
        //if(j == 1) b[j] = temp1%am;
        //else b[j] = (b[j-1]+temp1%am)%am;
    }
    for(int k = 1;k <= n;k++){    //维护一个代价前缀和数组
        if(k == 1) c[k] = (a[k]*b[k])%am;
        else c[k] = (c[k-1] + (a[k]*b[k])%am)%am;
    }
    for(int j = 2;j <= n;j++)    //维护一个货物前缀和数组
        b[j] = (b[j] + b[j-1])%am;
    
    int x,l,r;
    for(int s = 1;s <= m;s++){
        cin>>x>>l>>r;
        ll temp2,temp3;
        //分三种情形，注意若结果为负数应加上1e9+7
        if(x <= l){
            temp2 = c[r]-c[l-1] >= 0 ? c[r]-c[l-1] : (c[r]-c[l-1]+am);
            temp3 = b[r]-b[l-1] >= 0 ? b[r]-b[l-1] : (b[r]-b[l-1]+am);
            temp3 = (temp3*a[x])%am;
            cout<<(temp2-temp3 >=0 ? temp2-temp3 : (temp2-temp3+am))<<endl;
        }
        else if(x >= r){
            temp2 = c[r]-c[l-1] >= 0 ? c[r]-c[l-1] : (c[r]-c[l-1]+am);
            temp3 = b[r]-b[l-1] >= 0 ? b[r]-b[l-1] : (b[r]-b[l-1]+am);
            temp3 = (temp3*a[x])%am;
            cout<<(temp3-temp2 >=0 ? temp3-temp2 : (temp3-temp2+am))<<endl;
        }
        else{
            temp2 = c[r]-c[x] >= 0 ? c[r]-c[x] : (c[r]-c[x]+am);
            temp3 = c[x]-c[l-1] >= 0 ? c[x]-c[l-1] : (c[x]-c[l-1]+am);
            temp2 = temp2-temp3 >=0 ? temp2-temp3 : (temp2-temp3+am);
            temp3 = ((b[x]-b[l-1] >= 0 ? b[x]-b[l-1] : (b[x]-b[l-1]+am))*a[x])%am;
            temp2 = (temp2+temp3)%am;
            temp3 = ((b[r]-b[x] >= 0 ? b[r]-b[x] : (b[r]-b[x]+am))*a[x])%am;
            cout<<(temp2-temp3 >=0 ? temp2-temp3 : (temp2-temp3+am))<<endl;
        }
    }
    
    return 0;
}