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

题意：

给定一维数轴上 个点之间的距离 ，每个点储存一些货物 。
每次询问将一段区间 的货物全部移动到点 的代价和。
储物点 有 个货物，全部移动到点 的代价为 。

解法：

前缀和。

先根据 和 ， 之间的关系分情况讨论。

先写下第一种情况的计算式：

令 ，
则
令 ，
则：。

故只需要做三个前缀和数组 。就可以 计算出答案。

对于第二种情况：

计算式正好是情况一的计算式的相反数。

对于第三种情况，可以将区间拆分为 和 ，分别为情况二和情况一，分开计算然后求和就可以了。

Code：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
ll a[N], b[N], c[N], n, m;
ll calc(int x, int l, int r) {
    return ((c[r] - c[l - 1] - (b[r] - b[l - 1]) * a[x]) % mod + mod) % mod;
}
int main() {
    cin >> n >> m;
    for(int i = 2; i <= n; i++) {
        int x; cin >> x;
        a[i] = (x + a[i - 1]) % mod;
    }
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        b[i] = (x + b[i - 1]) % mod;
        c[i] = (x * a[i] + c[i - 1]) % mod;
    }
    while(m--) {
        int x, l, r, ans; cin >> x >> l >> r;
        if(x <= l) ans = calc(x, l, r);
        else if(x >= r) ans = (mod - calc(x, l, r)) % mod;
        else ans = (calc(x, x, r) + mod - calc(x, l, x - 1)) % mod;
        cout << ans << endl;
    }
    return 0;
}