P2367 语文成绩

题目

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

输入

第一行有两个整数 \(n\)，\(p\)，代表学生数与增加分数的次数。

第二行有 \(n\) 个数，\(a_1 \sim a_n\)，代表各个学生的初始成绩。

接下来 \(p\) 行，每行有三个数，\(x\)，\(y\)，\(z\)，代表给第 \(x\) 个到第 \(y\) 个学生每人增加 \(z\) 分。

输出

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

样例

输入

3 2
1 1 1
1 2 1
2 3 1

输出

2

提示

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

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

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

对于 \(100\%\) 的数据，有 \(n \le 5\times 10^6\)，\(p \le n\)，学生初始成绩 $ \le 100\(，\)z \le 100$。

思路

分析题意，知道老师要对某些区间进行加法操作，如果暴力计算会超时，于是转换为差分数组操作，最后做前缀和得到最终的结果。将问题转换为序列的差分问题，对差分数组区间位置的元素做“\(+z,-z\)”操作

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, a[5000010], c[5000010], sum[5000010], mn = 0x3f3f3f3f, x, y, z;

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
		c[i] = a[i] - a[i - 1];
	}
	for (int i = 1; i <= m; i ++ )
	{
		scanf("%d %d %d", &x, &y, &z);
		c[x] += z;
		c[y + 1] -= z;
	}
	for (int i = 1; i <= n; i ++ )
	{
		sum[i] = sum[i - 1] + c[i];
		if (sum[i] < mn)
			mn = sum[i];
	}
	printf("%d", mn);
	return 0;
}