1063 储物点的距离 - 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge

1063: 储物点的距离

时间限制：1.000s

内存限制：128MB

提交通过: 5 提交: 36 统计

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

第一行两个数表示n,m
第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离a_i
第三行n个数，表示每个储物点的东西个数b_i
之后m行每行三个数x l r

表示查询要把区间[l,r]储物点的物品全部运到储物点x的花费

每次查询独立

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

对于每个询问输出一个数表示答案
答案对1000000007取模

前缀和

提交