链接：https://ac.nowcoder.com/acm/contest/20960/1020
来源：牛客网

题目描述

 一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间[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取模

示例1

输入

复制5 5 2 3 4 5 1 2 3 4 5 1 1 5 3 1 5 2 3 3 3 3 3 1 5 5

5 5
2 3 4 5
1 2 3 4 5
1 1 5
3 1 5
2 3 3
3 3 3
1 5 5

输出

复制125 72 9 0 70

125
72
9
0
70

备注:

对于100%的数据n,m <= 200000 , 0 <= ai,bi <= 2000000000

本题需要经过查看之后找到移动方式去使用前缀和。最后再解法中可以分三种情况。

  1. 如果目标仓库在区间的左边：那么就是将区间里面到1仓库的花费减去区间仓库里面的数量和乘于目标仓库到1之间的距离。这样就是目标花费了。其实道理也很简单举一个例子比如从5到2之间的例子就可以了。
  2. 如果目标仓库在区间的右边：（目标仓库到1的距离*区间仓库的数量和）-（区间仓库到1的花费和）。
  3. 如果目标仓库在区间的中间，那么通过目标仓库分隔成左右两部分。注意如果目标仓库代入左边进行计算了那么右边需要将其排除掉。

除此之外本题中的数据量给的很大而且说明了需要将结果取余于1000000007。所以需要在计算过程中通过取余运算的一系列性质来在计算过程中取余，从而减少数据的大小防止越界。

取余运算的规则：

  1. （a+b）%p=(a%p+b%p)%p
  2. （a-b）%p=(a%p-b%p)%p。注意不能减成负数，通过(a%p+p)%p来调整
  3. （a*b）%p=(a%p*b%p)%p
  4. a^b%p=((a%p)^b)%p
  5. 结合律：（（a+b）%p+c）%p = （a+（b+c）%p）%p
  6. （（a*b）%p*c）%p = （a*（b*c）%p）%p
  7. 交换律：(a+b)%p=(b+a)%p
  8. (a*b)%p=(b*a)%p
  9. 分配率：((a+b)%p*c)%p = ((a*c)%p+(b*c)%p)%p

AC代码：

#include <bits/stdc++.h>
 
typedef long long ll;
 
using namespace std;
const ll MAXN = 2000005;
//计算距离的前缀和
ll dist[MAXN];
//计算所有仓库与1的运送成本
ll to_1[MAXN];
//计算运送成本的前缀和
ll cnt_to_1[MAXN];
//计算仓库中东西数目的前缀和
ll cnt_x[MAXN];
const ll p = 1000000007;
int main() {
    int n, m;
    cin>>n>>m;
    for (int i=2;i<=n;i++) {
        cin>>dist[i];
        dist[i] = (dist[i]+dist[i-1])%p;
    }
    for (int i=1;i<=n;i++) {
        cin>>cnt_x[i];
        //计算仓库到1的花费
        cnt_to_1[i] = (cnt_to_1[i-1]+dist[i]*cnt_x[i]%p)%p;
        //计算东西的前缀和
        cnt_x[i] = (cnt_x[i]%p+cnt_x[i-1]%p)%p;
    }
    //计算仓库到1的花费的前缀和
//     for (int i=1;i<=n;i++) {
//         cnt_to_1[i] = (cnt_to_1[i]%p+cnt_to_1[i-1]%p)%p;
//     }
    int x, r, l, t1, t2, t3;
    ll ans;
    for (int i=0;i<m;i++) {
        cin>>x>>l>>r;
        if (x<=l) {
            t1 = (cnt_to_1[r]%p-cnt_to_1[l-1]%p+p)%p;
            t2 = (cnt_x[r]%p-cnt_x[l-1]%p+p)%p;
            t3 = t2*dist[x]%p;
            ans = (t1-t3+p)%p;
        }
        else if (x>=r) {
            t1 = (cnt_to_1[r]%p-cnt_to_1[l-1]%p+p)%p;
            t2 = ((cnt_x[r]-cnt_x[l-1])+p)%p;
            t3 = t2*dist[x]%p;
            ans = (t3-t1+p)%p;
        } else {
            t2 = ((cnt_x[r]-cnt_x[x])+p)%p;
            t1 = (cnt_to_1[r]%p-cnt_to_1[x]%p+p)%p;
            t3 = t2*dist[x]%p;
            int left = (t1-t3+p)%p;
            t1 = (cnt_to_1[x]%p-cnt_to_1[l-1]%p+p)%p;
            t2 = (cnt_x[x]%p-cnt_x[l-1]%p+p)%p;
            t3 = t2*dist[x]%p;
            int right = (t3-t1+p)%p;
            ans = (left+right)%p;
        }
        cout<<ans<<endl;
    }
     
     
    return 0;
}