储物点的距离 _牛客博客

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

dist就是储物点间的距离。

题解：

首先将储物点之间的距离转换成在数轴上的点，a[i]:储物点在数轴上的位置，b[i]:储物点内物品数量；

将区间[l,r]内的储物点转移到x储物点，首先我们考虑l<=x<=r的情况；

$\sum_{i=l}^{x}{((a[x]-a[i])*b[i])}+\sum_{i=x+1}^{r}{((a[i]-a[x])*b[i])}$

可以化简为：

$a[x]*\sum_{i=l}^{x}{b[i]}-\sum_{i=l}^{x}{a[i]*b[i]}+\sum_{i=l+1}^{r}{a[i]*b[i]}-a[x]*\sum_{i=l+1}^{r}{b[i]}$

查询区间值的和——前缀和来处理这个式子：

令s1[i]=s1[i-1]+a[i]*b[i],s2[i]=s2[i]+b[i];

预处理之后，那么对于询问我们可以在O（1）时间内得出答案。

对于x<l和x>r的情况与上式相似，很容易得到。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int mod=1e9+7;
void io() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); }
ll a[maxn],b[maxn];
int n,m;
ll s1[maxn],s2[maxn];
int main() {
	scanf("%d%d",&n,&m);
	ll s=1,x=0,l,r,y;	
	for(int i=1;i<=n-1;i++){
		scanf("%lld",&x);
		a[i]=s; s+=x;
	}
	a[n]=s;
	for(int i=1;i<=n;i++){
		scanf("%lld",b+i);
	}
	for(int i=1;i<=n;i++){
		s2[i]=(s2[i-1]+b[i])%mod;
	}
	for(int i=1;i<=n;i++){
		s1[i]=(s1[i-1]+a[i]%mod*b[i])%mod;
	}
	ll ans=0;
	while(m--){
		scanf("%lld%lld%lld",&y,&l,&r);
		x=a[y]; //x储物点在数轴上的位置 
		ans=0;
		if(l<=y&&y<=r){
			ans=((x%mod*(s2[y]-s2[l-1])%mod-(s1[y]-s1[l-1]))%mod);
			ans=(ans+(((s1[r]-s1[y])-x%mod*(s2[r]-s2[y]))%mod))%mod;
		} else if(y<l){
			ans=((s1[r]-s1[l-1])-x%mod*(s2[r]-s2[l-1]))%mod;
		} else {
			ans=((x%mod*(s2[r]-s2[l-1])%mod-(s1[r]-s1[l-1])))%mod;
		}
		//处理答案为负数的情况 
		while(ans<0) ans=(ans+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}