NC14683 储物点的距离

题意

一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间 $[l,r]$ ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？
比如储物点 $i$ 有 $x$ 个东西，要运到储物点 $j$ ，代价为 $x * dist( i , j )$ 。 $dist$ 就是储物点间的距离。
对于 $100%$ 的数据 $n,m <= 200000 , 0 <= a_i,b_i <= 2000000000$

分析

总共有 $3$ 种情况，分别为：

$r \leq x$
$l \ge x$
$l\leq x \leq r$

假设在 $x$ 右边的范围为 $[l,r]$ 。
那么 $x$ 右边的东西搬到 $x$ 的总代价就为: $\sum\limits_{i=l}^{r}b_i*(a_i-a_x)$ ，展开一下，就是 $\sum\limits_{i=l}^{r}b_ia_i-a_x\sum\limits_{i=l}^{r}b_i$ 。
预处理一下 $a_ib_i$ 和 $b_i$ 的前缀和，就能 $O(1)$ 进行计算。
左边也是同理。

代码如下

#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int mod = 1e9 + 7;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
LL a[N], b[N], s[N], sum[N];
int main(){
    int i, j, x, l, r, k, n, m;
    n = read(); m = read();
    for(i = 2; i <= n; i++) a[i] = (a[i - 1] + read()) % mod;
    for(i = 1; i <= n; i++) b[i] = read();
    for(i = 1; i <= n; i++) s[i] = (s[i - 1] + b[i]) % mod, sum[i] = (sum[i - 1] + a[i] * b[i] % mod) % mod;
    while(m--){
        x = read(); l = read(); r = read();
        LL ans = 0;
        if(x >= r){
            ans = (ans + a[x] * (s[r] - s[l - 1]) % mod) % mod;
            ans = (ans - (sum[r] - sum[l - 1]))% mod;
            ans = (ans + mod) % mod;
            printf("%lld\n", ans);
        }
        else if(x <= l){
            ans = (ans + sum[r] - sum[l - 1]) % mod;
            ans = (ans - a[x] * (s[r] - s[l - 1]) % mod) % mod;
            ans = (ans + mod) % mod;
            printf("%lld\n", ans);
        }
        else{
            ans = (ans + sum[r] - sum[x - 1]) % mod;
            ans = (ans - a[x] * (s[r] - s[x - 1]) % mod) % mod;
            ans = (ans + a[x] * (s[x - 1] - s[l - 1]) % mod) % mod;
            ans = (ans - (sum[x - 1] - sum[l - 1])) % mod;
            ans = (ans + mod) % mod;
            printf("%lld\n", ans);
        }
    }
    return 0;
}