差分可视为对前缀和的一种逆运算,适用于数组中指定范围同时加/减同一个数时的效率优化,通过差分,时间复杂度可由O(n)降至O(1)

原题复现

https://www.luogu.com.cn/problem/P2367

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 nn，pp，代表学生数与增加分数的次数。

第二行有 nn 个数，a1∼ana_1 \sim a_n，代表各个学生的初始成绩。

接下来 pp 行，每行有三个数，xx，yy，zz，代表给第 xx 个到第 yy 个学生每人增加 zz 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例 #1

输入 #1

1
2
3
4
3 2
1 1 1
1 2 1
2 3 1

输出 #1

1
2
2

说明/提示

对于 40%40\% 的数据，有 n≤103n \le 10^3。

对于 60%60\% 的数据，有 n≤104n \le 10^4。

对于 80%80\% 的数据，有 n≤105n \le 10^5。

对于 100%100\% 的数据，有 n≤5×106n \le 5\times 10^6，p≤np \le n，学生初始成绩 ≤100 \le 100，z≤100z \le 100。

解题思路

题目涉及到多组区间的同加/减,适合使用差分算法
差分算法的核心逻辑是在原数组data[n]的基础上构建差分数组d[n],满足d[n] = data[n] - data[n-1]
当我们需要对data[l,r]中的所有数据同时加上val时,只需要执行

1
2
d[l] += val
d[r+1] -= val

多次区间加减则多次对差分数组上述操作即可,最好对差分数组d[n]求前缀和即可得到原数组

代码实现

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
import sys
import gc
from array import array

n,p = map(int,sys.stdin.readline().strip().split())
row = array('i',map(int,sys.stdin.readline().strip().split()))
d = array('i',[row[0]])

for i in range(1,n):
    d.append(row[i]-row[i-1])
    
row.clear()
del row
gc.collect()

for _ in range(p):
    x,y,z = map(int,sys.stdin.readline().strip().split())

    d[x-1] += z
    if y != n:
        d[y] -= z

for i in range(1,n):
    d[i] += d[i-1]

print(min(d))

这里真的优化到极致了喵~ 😭 用了快速读取、数组全部用array.array()构建、gc.collect()释放内存,但架不住还是有一组数据MLE了🥹

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
#include<iostream>
using namespace std;
int mini(int a[],int n){
    int mi = a[0];
    for(int i = 1 ; i < n ; i++)
        if(a[i] < mi)
            mi = a[i];
    return mi;
}
int main(){
    int n,p;
    cin >> n;
    cin >> p;
    int a[n] = {};
    for(int i = 0 ; i < n ; i++){ cin >> a[i]; }
    int d[n] = {a[0]};
    for(int i = 1 ; i < n ; i++) { d[i] = a[i] - a[i-1]; }
    for(int i = 0 ; i < p; i++){
        int x,y,z;
        cin >> x;
        cin >> y;
        cin >> z;
        d[x-1] += z;
        if(y != n) d[y] -= z;
    }
    for(int i = 1 ; i < n ; i++) d[i] += d[i-1];
    cout << mini(d,n);
}

换cpp用同样的思路随便AC,洒洒水啦喵~