北京的网站设计公司,北京网站域名备案查询,福州企业做网站,61制作工厂网站链接#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述 一个数轴#xff0c;每一个储物点会有一些东西#x…链接
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述 一个数轴每一个储物点会有一些东西同时它们之间存在距离。 每次给个区间[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
70备注: 对于100%的数据n,m 200000 , 0 ai,bi 2000000000
题解
先要意识到给的距离是两个相邻的储物点的距离我们可以据此先维护一个距离的前缀和这样我们就可以求任意两点之间的距离。 同理每个储物点都是存有物品的也用前缀和来维护这就可以求出某个区间内物品的总数量。 我们还需要用一个数组c来记录给定区间[l,r]内所有商品距离1号仓库的总和,c[i]c[i-1]a[i]*b[i], abc分别代表上面三个的前缀和 有什么用呢接着往下看
如果所给x在[l,r]的右边也就是xr当x从i变为i1相当于整个区间内的物品都多移动了一段距离长度为lenii1那我们就可从i点答案的基础上直接改从答案基础上加上[l,r]的物品数量 * len(i,i1)也就是 ( b [ r ] - b [ l - 1 ] ) * ( a [ x ] ) - ( c [ r ] - c[ l - 1 ] ) 怎么理解[l,r]这个区间内所有物品全部从起始点移动到x点[1,l-1]这一块是多移动了比如看l点从1 ~ l 再从l ~ x ,其中1~l是多移动的部分就要剪除l点物品总量*所有物品移动到点1的距离这不正是我们求得c所以减去( c [ r ] - c[ l - 1 ] )
如果x在[l,r]的左侧也就是xr当x从i变为i1,就是和上面反过来少移动了一段距离距离为len(i,i1),答案就是( c [ r ] - c[ l - 1 ] ) - ( b [ r ] - b [ l - 1 ] ) * ( a [ x ] )
如果x在[l,r]中间你就把[l,r]分成两个区域然后[l.x]与[x1r]用上面的方法对待 对了别忘了取模
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn2e55;
const ll mod1e97;ll a[maxn],b[maxn],c[maxn];
ll getr(ll x,ll l,ll r)//当x在右边
{ll ans(((b[r]-b[l-1])*a[x]%mod-((c[r]-c[l-1])%modmod)%mod)%modmod)%mod;return ans;
}
ll getl(ll x,ll l,ll r)//x在左边
{ll ans(((c[r]-c[l-1])%modmod)%mod-((b[r]-b[l-1])*a[x]%mod)%modmod)%mod;return ans;
}
ll x,l,r;
ll sum;
int main()
{int n,m;cinnm;for(int i2;in;i){cina[i];a[i](a[i-1]a[i])%mod;}for(int i1;in;i){cinb[i];c[i](c[i-1]a[i]*b[i]%mod)%mod;b[i](b[i]b[i-1])%mod;}while(m--){sum0;cinxlr;if(rx){sumgetr(x,l,r);}else if(lx){sumgetl(x,l,r);}else {sumgetr(x,l,x)getl(x,x1,r);}printf(%lld\n,sum%mod);}return 0;
}
