储物点的距离 题解

这道题其实就是一道化式子的题，化完式子后就可以乱搞了/x

我们设pos[i]表示i号点的位置，特别的，pos[1]=0,那么，我们就可以根据i到i+1的距离，分别算出每个点的位置了。

那么，我们就开始化式子吧。

我们假设将i号点的物品搬到j号点去，那么代价就是：

那么， 如果将l-r号点的物品搬到x号点去，代价就是：

我们发现，绝对值太烦了，于是我们想办法化掉绝对值，那么，我们只需要分情况讨论就行了：

1.x<=l，那么，对于任意的来说，都有,于是式子变为：

注意到，对于任意的点i来说，是个常数，所以，我们设,那么，我们就相当于求所有的b[i]的和，然后，后面的式子，明显就是所有的a[i]的和乘一个pos[x]这个常数，于是，我们就可以搞个前缀和之类的直接计算了

2.x>=r,这个和上面的几乎一模一样，只是减数和被减数交换了一下罢了。

3.l<x<r,这个情况，我们就将询问拆成两个来做就行了。

拆成：l-(x-1)搬到x的代价和(x+1)-r搬到x的代价（x搬到x的代价一定是0，不算也行）

就可以还是使用上面的方法来分别计算了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1,mod=1e9+7;
int a[N],W[N],S[N],pos[N];
inline pair<int,int>find(int l,int r){
    return make_pair((W[r]-W[l-1])%mod,(S[r]-S[l-1])%mod);
}
signed main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=2;i<=n;++i){
        scanf("%lld",&pos[i]);pos[i]=(pos[i]+pos[i-1])%mod;
    }
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        W[i]=(W[i-1]+a[i])%mod;S[i]=(1LL*a[i]*pos[i])%mod;S[i]=(S[i]+S[i-1])%mod;
    }
    while(m--){
        int l,r,x,ans=0;
        scanf("%lld%lld%lld",&x,&l,&r);
        if(l>=x){
            pair<int,int>res=find(l,r);
            ans=res.second;
            ans-=(1LL*pos[x]*res.first)%mod;
            ans=(ans%mod+mod)%mod;
            printf("%lld\n",ans);
        }else if(r<=x){
            pair<int,int>res=find(l,r);
            ans=(1LL*pos[x]*res.first)%mod;
            ans-=res.second;
            ans=(ans%mod+mod)%mod;
            printf("%lld\n",ans);
        }else{
            pair<int,int>res1=find(l,x-1),res2=find(x+1,r);
            int ans1=(1LL*pos[x]*res1.first)%mod,ans2=res2.second;
            ans1-=res1.second,ans2-=(1LL*pos[x]*res2.first)%mod;
            ans1=(ans1%mod+mod)%mod,ans2=(ans2%mod+mod)%mod;
            printf("%lld\n",(ans1+ans2)%mod);
        }
    }
    return 0;
}

Ps:我之前还想到了一个不那么优秀的但是很好理解的算法——分块

我们预处理出同一个块中，每个点跑到块的左端点和右端点的代价，然后询问的时候，将询问区间中相应的点按照块所在的区间和x的相对位置来考虑将代价叠加到块的左端点还是右端点还是直接到x。

叠加完后，因为最多就个块，所以，就相对于询问最多个点到x的代价，那么直接暴力统计即可