【每日一题】5月15日 储物点的距离

题目:
一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间 ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？
比如储物点 有 个东西，要运到储物点 ，代价为
就是储物点间的距离。

表示第i个储物点与第i+1个储物点的距离
表示每个储物点的东西个数

分析：
对于区间的物品移动到第位置,显然是
.
因为是多组询问显然是不可能直接暴力计算的.
以为 是在变化的，我们可以预处理所有物品移动到指定的一个点的价值,我们指定移动到第一个物品的位置,根据位置先后维护移动代价的前缀和.
那么移动位置从第物品的位置 变成了 物品的位置。

• 假如对于询问区间 , ,那么与我们预处理的代价，多了 区间物品的数量乘以 的代价.显然我们还要维护一个物品个数的前缀和，维护一个移动前i位置的物品代价前缀和,方便查询进行计算.
• 假如对于询问区间 , ,我们转换一下思维，假如的物品在 位置了，要将它们还原到原位置，代价其实就是 区间物品的数量乘以 位置到 的距离 减去将区间物品移动到 位置的代价.
• 那么对于 的情况,只需要将区间分成 两部分按照上面讨论算代价累加起来即可。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=2e5+10;
const int mod=1e9+7;

ll n,m;
ll num[maxn],a[maxn],b[maxn],sum[maxn];

int main()
{
    cin>>n>>m;
    for( int i=2;i<=n;i++ )
    {
        cin>>a[i];
        a[i]=(a[i]+a[i-1])%mod;
    }        
    for( int i=1;i<=n;i++ )
    {
        cin>>num[i];
        sum[i]=(a[i]*num[i]%mod+sum[i-1])%mod;
        num[i]=(num[i]+num[i-1])%mod;
    }
    while( m-- )
    {
        int x,l,r;
        cin>>x>>l>>r;
        ll ans=0;
        if( x<=l )
        {
            ans=(sum[r]-sum[l-1]+mod)%mod;
            ans=(ans-(num[r]-num[l-1]+mod)%mod*a[x]%mod+mod)%mod;
        }
        else if( x>=r )
        {
            ans=((num[r]-num[l-1]+mod)%mod*a[x]%mod-(sum[r]-sum[l-1]+mod)%mod+mod)%mod;
        }
        else
        {
            ans=(sum[r]-sum[x-1]+mod)%mod;
            ans=(ans-(num[r]-num[x-1]+mod)%mod*a[x]%mod+mod)%mod;
            ans=(ans+(num[x]-num[l-1]+mod)%mod*a[x]%mod-(sum[x]-sum[l-1]+mod)%mod+mod)%mod;
        }
        ans=(ans+mod)%mod;
        cout<<ans<<endl;
    }

}