分类目录归档：差分数组

洛谷 海底高铁

发表评论

题号：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]来表示了。