Blackops

初心易得，始终难守

0%

牛客练习赛8 B 储物点的距离（前缀和+思维）

发表于 更新于 分类于 ，

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间[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取模
示例1
输入

5 5
2 3 4 5
1 2 3 4 5
1 1 5
3 1 5
2 3 3
3 3 3
1 5 5
输出

125
72
9
0
70
备注:
对于100%的数据n,m <= 200000 , 0 <= ai,bi <= 2000000000

题目链接：B.储物点的距离
题意就是给你$n$个点的位置$p_i$和其点上的物品个数$b_i$，每次询问$\Sigma_{i=l}^{r}{b_i \times \lvert p_i-p_x \rvert}$。
显然这里的求和公式是可以拆成：$b_i \times \Sigma_{i=l}^r p_i- b_i \times {\Sigma_{i=l}^r p_x}$，然后预处理出$\Sigma b_i$和$\Sigma p_i \times b_i$的两个前缀和，然后分三类讨论一下

  1. $x \ge r$, $ans = p_x \times \Sigma_l^r{b_i} - \Sigma_l^r{p_i \times b_i}$
  2. $x \le l$, $ans = \Sigma_l^r{p_i*b_i} - p_x \times \Sigma_l^r{b_i}$
  3. $l \lt x \lt r$, $ans = \Sigma_x^r{p_i \times b_i} -p_x \times \Sigma_x^r{b_i} + p_x \times \Sigma_l^{x-1}b_i - \Sigma_l^{x-1}b_i \times p_i$

最恶心的是负数的取模，这里一旦弄错很可能一组数据都过不了（开始怀疑人生）……，负数取模可以先取模，再加模数，再取模即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
const LL mod = 1000000007LL;
LL pos[N], b[N], sb[N], pos_b[N];

LL mul(LL a, LL b)
{
    LL r = 0;
    while (b)
    {
        if (b & 1)
            r = (r + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return r;
}
inline LL S(LL arr[], int l, int r)
{
    return (arr[r] - arr[l - 1]) % mod;
}
int main(void)
{
    int n, m, i;
    scanf("%d%d", &n, &m);
    pos[1] = 0;
    for (i = 1; i < n; ++i)
    {
        LL d;
        scanf("%lld", &d);
        pos[i + 1] = (pos[i] + d) % mod;
    }
    for (i = 1; i <= n; ++i)
        scanf("%lld", &b[i]);
    for (i = 1; i <= n; ++i)
    {
        pos_b[i] = (pos_b[i - 1] + mul(pos[i], b[i])) % mod;
        sb[i] = (sb[i - 1] + b[i]) % mod;
    }
    while (m--)
    {
        int x, l, r;
        scanf("%d%d%d", &x, &l, &r);
        if (x >= r)
        {
            LL ans = mul(S(sb, l, r), pos[x]) - S(pos_b, l, r);
            printf("%lld\n", (ans % mod + mod) % mod);
        }
        else if (x <= l)
        {
            LL ans = S(pos_b, l, r) - mul(S(sb, l, r), pos[x]);
            printf("%lld\n", (ans % mod + mod) % mod);
        }
        else
        {
            LL ans = S(pos_b, x, r) - mul(S(sb, x, r), pos[x]);
            LL ans2 = mul(S(sb, l, x - 1), pos[x]) - S(pos_b, l, x - 1);
            ans = ((ans + ans2) % mod + mod) % mod;
            printf("%lld\n", ans);
        }
    }
    return 0;
}