储物点的距离

题目描述

一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？
比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j )
dist就是储物点间的距离。

输入描述:
第一行两个数表示n,m

第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离ai

第三行n个数，表示每个储物点的东西个数bi

之后m行每行三个数x l r

表示查询要把区间[l,r]储物点的物品全部运到储物点x的花费
每次查询独立
输出描述:
对于每个询问输出一个数表示答案
答案对1000000007取模

思路：
前一段有一题和这题差不多
https://ac.nowcoder.com/acm/problem/205912

我们不妨设第一个点坐标为1
根据题意得输入，把a[i]进行前缀和一下，这样可以计算出每个点距离第一个点的距离。
b[i]是每个位置的物品数，我们同样进行前缀和，可以算出区间有多少个数。
再开一个数组c，用来记录前i个地方的物品距离原点0的距离和。
预处理完之后。每次询问就可以进行O(1)查询了
如果x<=l c[r]-c[l-1]可以算出区间[l,r]的所有物品距离原点的和。
因为这些点最后都要到a[x]这个位置，而区间物品数量是b[r]-b[l-1]
那么最后的距离原点和就是(b[r]-b[l-1]) * x,所以c[r]-c[l-1]-(b[r]-b[l-1]) * x就是该次查询的答案。
同理 如果x>=r 答案就是(b[r]-b[l-1]) * x-c[r]-c[l-1]
如果x在[l,r]之间 把x作为分界点，分成两个区间按照前两个情况计算求和即可。
注意减法取模

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mod=1000000007;
ll a[N],b[N],c[N];
int main(){
    int n,m;cin>>n>>m;
    a[1]=1;
    for(int i=2;i<=n;i++){
        cin>>a[i];
        a[i]=(a[i-1]+a[i])%mod;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        c[i]=(c[i-1]+a[i]*b[i])%mod;
        b[i]=(b[i]+b[i-1])%mod;
        //cout<<i<<" "<<a[i]<<endl;
    }
    while(m--){
         ll x,l,r;cin>>x>>l>>r;
         ll sum;
        if(r<=x){
            sum=(((b[r]-b[l-1])*a[x]%mod-((c[r]-c[l-1])%mod+mod)%mod)%mod+mod)%mod;
        }
        else if(l>=x){
            sum=(((c[r]-c[l-1])%mod+mod)%mod-((b[r]-b[l-1])*a[x]%mod)%mod+mod)%mod;
            //cout<<" "<<c[r]-c[l-1]<<" "<<b[r]-b[l-1]<<" "<<a[r]<<endl;
        }
        else {
            sum=(((b[x]-b[l-1])*a[x]%mod-((c[x]-c[l-1])%mod+mod)%mod)%mod+mod)%mod;
            sum+=(((c[r]-c[x])%mod+mod)%mod-((b[r]-b[x])*a[x]%mod)%mod+mod)%mod;
        }
        cout<<sum%mod<<endl;
    }
    return 0;
}