中企动力设计的网站,一个叫mit做app的网站,首京建设投资引导基金网站,做微商建自己的网站有用吗链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述 一个数轴#xff0c;每一个储物点会有一些东西#xff0c;同时它们之间存在距离。 每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少#xff1…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述 一个数轴每一个储物点会有一些东西同时它们之间存在距离。 每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少 比如储物点i有x个东西要运到储物点j代价为x * dist( i , j ) dist就是储物点间的距离。 输入描述:
第一行两个数表示n,m
第二行n-1个数第i个数表示第i个储物点与第i1个储物点的距离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
输出
复制125 72 9 0 7125 72 9 0 70
备注:
对于100%的数据n,m 200000 , 0 ai,bi 2000000000还有减号取模为a-bmod%mod因为减可能为负数
#includebits/stdc.h
using namespace std;
using lllong long;
const ll mod1000000007;//qu
ll a[200005],b[200005],s[200005];
ll right(int l,int r,int x){//在左边return ((s[r]-s[l-1])-a[x]*(b[r]-b[l-1]))%mod;//把区间到1点的前缀和算出来然后减去1到x的多余前缀和
}
ll left(int l,int r,int x){//在右边return (a[x]*(b[r]-b[l-1])-(s[r]-s[l-1]))%mod;//与上面相反
}
int main(){int n,m;cinnm;for(int i2;in;i){//各点到1点的距离ll num;cinnum;a[i](a[i-1]num)%mod;}for(int i1;in;i){cinb[i];s[i](s[i-1]b[i]*a[i])%mod;//各点转移到1点的代价b[i](b[i-1]b[i])%mod;//区间物品数量}for(int i1;im;i){ int x,l,r;cinxlr;ll ans0;if(xl)ansright(l,r,x);else if(xr)ansleft(l,r,x);else ansleft(l,x,x)right(x,r,x);cout(ans%modmod)%modendl;}
}
