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

题意：

给定一维数轴上 $n$ 个点之间的距离 $a_i$ ，每个点储存一些货物 $b_i$ 。
每次询问将一段区间 $[l, r]$ 的货物全部移动到点 $x$ 的代价和。
储物点 $i$ 有 $x$ 个货物，全部移动到点 $j$ 的代价为 $x * dist(i, j)$ 。

解法：

前缀和。

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

$x \leq l$
$x \geq r$
$l < x < r$

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

$ans = \sum \limits_{i=l}^{r} b_i * dist(i, x) = \sum \limits_{i=l}^{r} b_i \sum \limits_{j=x}^{i-1} a_j$

令 $c_i = \sum \limits_{j=1}^{i-1} a_j$ ，
则 $ans = \sum \limits_{i=l}^r b_i (c_i - c_x) = \sum \limits_{i=l}^r (b_ic_i - b_ic_x) = (\sum \limits_{i=l}^r b_ic_i) - (c_x \sum \limits_{i=l}^r b_i)$
令 $d_i = \sum \limits_{j=1}^{i}b_j, e_i = \sum \limits_{j=1}^ic_jb_j$ ，
则： $ans = (e_r-e_{l-1}) - c_x (d_r - d_{l-1})$ 。

故只需要做三个前缀和数组 $c_i, d_i, e_i$ 。就可以 $O(1)$ 计算出答案。

对于第二种情况：

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

对于第三种情况，可以将区间拆分为 $[l, x-1]$ 和 $[x, r]$ ，分别为情况二和情况一，分开计算然后求和就可以了。

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;
}