每日一题：储物点的距离

题意

给定 $i$ 和 $i+1$两点的距离和 $i$ 点的货物数量，$m$ 次询问将 $[l,r]$ 所有物品搬到 $x$ 点的总费用（区间内每个物品各自离 $x$ 点距离和）。（$n,m <= 200000 , 0 <= ai,bi <= 2000000000$）

soltuion

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

• $x<=l$，即 $[l,r]$ 所有物品到原点的距离 - 到 $x$ 点的距离。
• $x>=r$，即 $[l,r]$ 所有物品从 $x$ 点到原点的距离 - 从原位置到原点的距离。
• 处于中间的情况，就是拆解成 $[l,x],[x+1,r]$ 两种情况，然后分别带入上面情况即可。

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