NC14683 储物点的距离

题目地址：

https://ac.nowcoder.com/acm/problem/14683

基本思路：

比较经典的前缀和应用，我们先将输入中前后两个储物点的距离，转化一次前缀和存在数组a中，这时候既可以将储物点定位在数轴中，然后 $i$ , $j$ 两点间的运送代价即为： $b[i] * |a[j] - a[i]|$ 那么区间 $[l,r]$ 内的东西转移到 $x$ 的的代价和即为 $\sum_{i = l} ^ {r}b[i] * | a[x] - a[i]|$ ，也就是 $|a[x]* \sum_{i = l} ^ {r} b[i] - \sum_{i = l} ^ {r}b[i]*a[i]|$ 前半部分我们求一下 $b[i]$ 的前缀和就能每次O(1)求到，同理后半部分我们求 $a[i]*b[i]$ 的前缀和也能每次O(1)求到，因此我们只要讨论一下这个绝对值的情况就是了，这部分可以画个数轴辅助一下理解，应该不难，然后就是注意取模有负数。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 2e5 + 20;
const int mod = (int)1e9 + 7;
int n,m,a[maxn],b[maxn],sum[maxn],par[maxn];
signed main() {
  IO;
  cin >> n >> m;
  a[1] = 0;
  rep(i,2,n) cin >> a[i],a[i] = (a[i-1] + a[i]) % mod;
  rep(i,1,n) cin >> b[i],par[i] = (par[i-1] + b[i]) % mod;//b[i]的前缀和;
  rep(i,1,n){
    sum[i] = (sum[i-1] + a[i] * b[i]) % mod;//a[i]*b[i]的前缀和;
  }
  while(m--){
    int x,l,r;
    cin >> x >> l >> r;
    //三种情况分类讨论;
    if(x <= l){
      int k1 = (par[r] - par[l - 1] + mod) % mod * a[x] % mod;
      int k2 = (sum[r] - sum[l-1] + mod) % mod;
      int ans = (k2 - k1 + mod) % mod;
      while(ans < 0) ans += mod;
      ans %= mod;
      cout << ans << '\n';
    }else if(x >= r){
      int k1 = (par[r] - par[l - 1] + mod) % mod * a[x] % mod;
      int k2 = (sum[r] - sum[l-1] + mod) % mod;
      int ans = (k1 - k2 + mod) % mod;
      while(ans < 0) ans += mod;
      ans %= mod;
      cout << ans << '\n';
    }else{
      int k1 = a[x] * (par[x] - par[l-1] + mod) % mod - (sum[x] - sum[l-1] + mod) % mod;
      int k2 = (sum[r] - sum[x-1] + mod) % mod - a[x] * (par[r] - par[x - 1] + mod) % mod;
      int ans = (k1 + k2) % mod;
      while(ans < 0) ans += mod;
      ans %= mod;
      cout << ans << '\n';
    } 
  }
  return 0;
}