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

题意

给定 和 两点的距离和 点的货物数量， 次询问将 所有物品搬到 点的总费用（区间内每个物品各自离 点距离和）。（）

soltuion

前缀和维护： 表示每个储物点离原点0的距离， 表示前 个储物点共有多少货物， 表示前 个储物点的所有物品到原点0的和。

• ，即 所有物品到原点的距离 - 到 点的距离。
• ，即 所有物品从 点到原点的距离 - 从原位置到原点的距离。
• 处于中间的情况，就是拆解成 两种情况，然后分别带入上面情况即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int N = 2e5 + 5;
int n, m, l, r;
ll x, res, sum1[N], sum2[N], sum3[N];
int main() {
  cin >> n >> m;
  for (int i = 2; i <= n; i++) {
    cin >> x;
    sum1[i] = (sum1[i - 1] + x) % mod;
  }
  for (int i = 1; i <= n; i++) {
    cin >> x;
    sum2[i] = (sum2[i - 1] + x) % mod;
    sum3[i] = (sum3[i - 1] + sum1[i] * x) % mod;
  }
  while (m--) {
    cin >> x >> l >> r;
    if (x <= l)
      res = ((sum3[r] - sum3[l - 1] + mod) % mod -
             (sum2[r] - sum2[l - 1] + mod) % mod * sum1[x] % mod + mod) %
            mod;
    else if (x >= r)
      res = ((sum1[x] * ((sum2[r] - sum2[l - 1] + mod) % mod)) % mod - sum3[r] +
             sum3[l - 1] + mod) %
            mod;
    else {
      res = (((sum3[r] - sum3[x] + mod) % mod -
              (sum2[r] - sum2[x] + mod) % mod * sum1[x] + mod) %
                 mod +
             ((sum1[x] * ((sum2[x] - sum2[l - 1] + mod) % mod)) % mod -
              sum3[x] + sum3[l - 1] + mod) %
                 mod) %
            mod;
    }
    cout << (res + mod) % mod << '\n';
  }
  return 0;
}