Distance of nowcoder content storage point

Title Description

There will be something for each storage point along a number axis, and there will be a distance between them.
Given an interval [l,r] at a time, what is the cost of querying to get everything in that interval to another storage point?
For example, Storage Point I has x items, which are shipped to Storage Point J at the cost of X * dist (i, j)
dist is the distance between storage points.

Enter a description:
The first two numbers in the row represent n,m

Number n-1 i n the second row, number I represents the distance ai between the ith and the i+1 storage points

Number of n in the third row, representing the number of things bi per storage point

The next m lines have three X L per line

Indicates the cost of the query to transport all items from an interval [l,r] storage point to storage point x
Independent per query
Output description:
Output a number for each query to indicate the answer
Answer to 1000000007 Modeling
Example 1
input
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
output
125
72
9
0
70
Remarks:
For 100% data n, m <= 200000, 0 <= ai, Bi <= 2000000000

Topic Analysis: Use prefix sum to solve interval problems.
When x<=l, the cost of interval [l,r] to x equals the cost of interval [l,r] to 1, minus the cost of weight [l,r] from 1 to n
When x>=r, the cost of the interval [l,r] to n is equal to the cost of the interval [l,r] to n, minus the cost of the weight [l,r] from n to X
The cost of other intervals [l,r] to X is divided into two parts [l,x-1] to X and [x+1,r] to X

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int maxn=2*1e5+100;
ll dis[maxn],Left[maxn],Right[maxn],b[maxn],sum_b[maxn],cost_l[maxn],cost_r[maxn];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Left[1]=0;
        for(int i=2;i<=n;i++)
        {
            scanf("%lld",&dis[i]);
            Left[i]=(Left[i-1]+dis[i])%mod; //Left Distance
        }
        Right[n]=0;
        for(int i=n-1;i>=1;i--)
        {
            Right[i]=(Right[i+1]+dis[i+1])%mod; //Right Distance
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
            sum_b[i]=(sum_b[i-1]+b[i])%mod;// Weight prefix and
        }
        cost_l[1]=0;
        for(int i=2;i<=n;i++)
        {
            cost_l[i]=(cost_l[i-1]+b[i]*Left[i])%mod; //Prefetch i Items to1Cost
        }
        cost_r[n]=0;
        for(int i=n-1;i>=1;i--)
        {
            cost_r[i]=(cost_r[i+1]+b[i]*Right[i])%mod; // Prefetch i Items to n Cost
        }
        ll x,l,r,ans;

        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&x,&l,&r);
            ans=0;
            if(l>=x)
            {
                ans=(cost_l[r]-cost_l[l-1]-(sum_b[r]-sum_b[l-1])*Left[x]+mod)%mod;
            }
            else if(r<=x)
            {
                ans=(cost_r[l]-cost_r[r+1]-(sum_b[r]-sum_b[l-1])*Right[x]+mod)%mod;
            }
            else
            {
                ans=(cost_r[l]-cost_r[x]-(sum_b[x-1]-sum_b[l-1])*Right[x]+mod)%mod;
                ans=(ans+(cost_l[r]-cost_l[x]-(sum_b[r]-sum_b[x])*Left[x]+mod)%mod+mod)%mod;
            }

            printf("%lld\n",(ans+mod)%mod);
        }
    }
    return 0;
}

Posted on Sun, 03 May 2020 01:24:18 -0700 by CleoK