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

储物点的距离

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

题目

题目描述：
一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？
比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j )
dist就是储物点间的距离。

输入描述：
第一行两个数表示n,m
第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离ai
第三行n个数，表示每个储物点的东西个数bi
之后m行每行三个数x，l，r
表示查询要把区间[l,r]储物点的物品全部运到储物点x的花费，每次查询独立

输出描述：
对于每个询问输出一个数表示答案。
答案对1000000007取模。

解析

这道题对一个区间快速求和，我们当然一看到就会想到用前缀和啦。

但是看这道题没发现要用这么多前缀和：

首先，我们要求区间的长度，当然就要一个前缀和（dis数组）。然后我们要知道某个区间内物品的数量，又要用一个前缀和（num数组）。
不过但是如果我们只考虑用用这两个进行计算，肯定会超时：我们要遍历一遍区间内的每个点进行遍历计算求和。
但是说到区间遍历计算求和！我们岂不是又能创造一个前缀和！！！
所以我们可以再用一个前缀和保存某一个点到原点的前缀和（前缀和相减就相当于某个区间到原点的代价）。

取模运算注意：

由于题目出现了：由于数据过大所以对mod取模。这里我们就要注意了！
取模运算的加法就是加起来取模就行了。减法就不一样了，减法可能会减出负数来，所以每一次减法都一定要进行+mod再取模，使其为正数。
其他等同的就是，乘法没什么。除法就不一样了，我们就要用到逆元（这里不用，就不展开）。

算法操作：

首先就是前缀和的创建咯：

长度的前缀和就不多说，直接看一下代码：

for (int i = 2; i <= n; i++) {
    cin >> dis[i];
    dis[i] = (dis[i] + dis[i - 1]) % MOD;
}

小重点是到原点的前缀和怎么建立：

for (int i = 1; i <= n; i++) {
    cin >> num[i];
    w[i] = (w[i - 1] + dis[i] * num[i]) % MOD;
    num[i] = (num[i] + num[i - 1]) % MOD;
}
//因为我们不需要每个点的值，所以我们对个数前缀和与到原点的代价前缀和同时初始化
//同时操作是因为我们求代价是用单点的个数，而非前缀和
//上面的dis[i]就是到原点的距离，num[i]就是单点的个数，所以累加起来就好了

既然我们已经知道前缀和怎么得到以后，就是该怎么用前缀和进行计算了！
首先我们假设 l 表示区间左端，r 表示区间右端。x表示我们的终点。我们现在假设x一点在 l ~ r 外面（因为即使在中间，把这个区间分成两段，对于左右两段他还是在外面）。

假如x在区间左边：我们既然已经有前缀和当然想到用前缀和。如果用前缀和是什么呢？相当于x = 1时的代价了，所以如果x > 1，我们只要把这个区间在1~x的部分减掉就好了：

ans = (w[r] - w[l - 1] + MOD) % MOD;
//我们先求出了这个区间到1的前缀和
ans = (ans - (num[r] - num[l - 1] + MOD) % MOD * dis[x] % MOD + MOD) % MOD;
//然后这里减去多余的部分：也就是这个区间的点数 * 1到x的距离（多余的长度）。

那假如在右边呢？我们依旧是用右边的区间减去左边的多余了：也就是先算出区间在这一整段（1~x）的代价，再减去从1到每个点的代价（也就是前缀和之差）。

ans = (num[r] - num[l - 1] + MOD) % MOD * dis[x] % MOD;
//先求出区间在1~x的总代价
ans = (ans - (w[r] - w[l - 1] + MOD) % MOD + MOD) % MOD;
//减去1~前面每个点的代价

左右已经知道了，但是现在 l 和 r 是确定的数，所以还是有x在区间中间的情况，那再中间的咋办呢？

我刚刚讲了一句话，可以拆成两段，那好，我们就是拆成两段来算：左边就是 l ~ x ，右边就是 x ~ r 。分别进行计算再加起来就好啦：

ans = (w[r] - w[x] + MOD) % MOD;
ans = (ans - (num[r] - num[x] + MOD) % MOD * dis[x] % MOD + MOD) % MOD;
ans = (ans + (num[x] - num[l - 1] + MOD) % MOD * dis[x] % MOD) % MOD;
ans = (ans - (w[x] - w[l - 1] + MOD) % MOD + MOD) % MOD;

看，是不是就是重复了上面的操作！

讲了这么多，打代码吧：

首先初始化前缀和，在上面小专栏已经讲啦。
然后就是分点计算惹，算法讲解也讲啦哈哈哈。
看代码趴~

（什么？你问我这个板块有啥意义？就是把步骤连起来看的清楚点哈哈哈哈哈）

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 2e5 + 7;
ll dis[MAX], num[MAX], w[MAX];
//全局变量区


int main() {
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 2; i <= n; i++) {
        cin >> dis[i];
        dis[i] = (dis[i] + dis[i - 1]) % MOD;
    }
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        w[i] = (w[i - 1] + dis[i] * num[i]) % MOD;
        num[i] = (num[i] + num[i - 1]) % MOD;
    }
    while (m--) {
        int x, l, r; cin >> x >> l >> r;
        ll ans = 0;
        if (x <= l) {
            ans = (w[r] - w[l - 1] + MOD) % MOD;
            ans = (ans - (num[r] - num[l - 1] + MOD) % MOD * dis[x] % MOD + MOD) % MOD;
        }
        else if (x >= r) {
            ans = (num[r] - num[l - 1] + MOD) % MOD * dis[x] % MOD;
            ans = (ans - (w[r] - w[l - 1] + MOD) % MOD + MOD) % MOD;
        }
        else {
            ans = (w[r] - w[x] + MOD) % MOD;
            ans = (ans - (num[r] - num[x] + MOD) % MOD * dis[x] % MOD + MOD) % MOD;
            ans = (ans + (num[x] - num[l - 1] + MOD) % MOD * dis[x] % MOD) % MOD;
            ans = (ans - (w[x] - w[l - 1] + MOD) % MOD + MOD) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏