分类目录归档:差分数组

洛谷 海底高铁

题号:P3406
把数据类型都开成long long,不然等着丢分??

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
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
long long track_dif[100005], track[100005];
long long P[100005];
long long A[100005], B[100005], C[100005];
long long cost;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> P[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for (int i = 1; i <= m - 1; i++){
        int l = min(P[i], P[i + 1]), r = max(P[i], P[i + 1]);
        track_dif[l]++;
        track_dif[r]--;
    }
    for (int i = 1; i <= n - 1; i++){
        track[i] = track[i - 1] + track_dif[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cost += min(track[i] * A[i], C[i] + track[i] * B[i]);
    }
    cout << cost;
}

差分数组的学习

今天在洛谷八连测R2的群里讨论T2时,遇到了这个问题。搞了半天才弄懂,在这里总结一下,免得以后再要用就忘了。
先出一个问题:
给定一个长度为N的序列A:首先进行X次操作,每次操作在Li和Ri这个区间加上一个数Ci。
进行Y次询问,每次询问Li到Ri的区间和。
有人会说这是树状数组/线段树的裸题,直接用树状数组/线段树去写。但是因为线段树/树状数组不是特别好写(到现在也不会线段树/树状数组好长时间没打忘光了),所以有人就就想出来差分数组这么一个好办法来解决这个问题。
首先,请注意!差分数组的使用是有条件的!我上面所提到的问题因为是离线的,所以可以使用差分数组,而如果是在线的问题,差分数组就不要用了,还是乖乖的去写线段树吧。
大家应该都知道前缀和,而差分数组本质上是前缀和的逆运算,前缀和是加号,而差分数组在推导的时候,则是减号。
对于上面的问题,我们将序列A[n]进行差分,设差分数组D[i]=D[i]-D[i-1]。差分数组推导完毕之后,进行区间加减操作。
假设我们要在闭区间[l,r]上统一加上值k,那么我们只需:令D[l]+=k;D[r+1]-=k即可。然后对D[n]进行前缀和操作,生成数组A[n],再对A[n]进行前缀和操作,生成数组B[n]。那么闭区间[Li,Ri]的区间和就可用B[Ri]-B[Li-1]来表示了。