鏈接：

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

時間限制：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個儲物點與第i+1個儲物點的距離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],
a，b，c分別代表上面三個的前綴和
有什么用呢？接著往下看

如果所給x在[l,r]的右邊，也就是x>=r，當x從i變為i+1，相當于整個區間內的物品都多移動了一段距離，長度為len（i，i+1），那我們就可從i點答案的基礎上直接改，從答案基礎上加上[l,r]的物品數量 * len(i,i+1)，也就是 ( 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]的左側，也就是x<=r，當x從i變為i+1,就是和上面反過來，少移動了一段距離，距離為len(i,i+1),答案就是( c [ r ] - c[ l - 1 ] ) - ( b [ r ] - b [ l - 1 ] ) * ( a [ x ] )

如果x在[l,r]中間，你就把[l,r]分成兩個區域，然后[l.x]與[x+1，r]用上面的方法對待
對了，別忘了取模

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5; const ll mod=1e9+7;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])%mod+mod)%mod)%mod+mod)%mod;return ans; } ll getl(ll x,ll l,ll r)//x在左邊 {ll ans=(((c[r]-c[l-1])%mod+mod)%mod-((b[r]-b[l-1])*a[x]%mod)%mod+mod)%mod;return ans; } ll x,l,r; ll sum; int main() {int n,m;cin>>n>>m;for(int i=2;i<=n;i++){cin>>a[i];a[i]=(a[i-1]+a[i])%mod;}for(int i=1;i<=n;i++){cin>>b[i];c[i]=(c[i-1]+a[i]*b[i]%mod)%mod;b[i]=(b[i]+b[i-1])%mod;}while(m--){sum=0;cin>>x>>l>>r;if(r<=x){sum=getr(x,l,r);}else if(l>=x){sum=getl(x,l,r);}else {sum+=getr(x,l,x)+getl(x,x+1,r);}printf("%lld\n",sum%mod);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客网【每日一题】5月15日题目 储物点的距离的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。