这道题其实就是一道化式子的题,化完式子后就可以乱搞了/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的代价,那么直接暴力统计即可