A18829. 区间修改求最值
填空题
较难
知识点
题目描述
区间修改求最值
题目描述
给定长度为 n 的初始数组，先进行 m 次区间加操作，所有操作完成后，求出数组中的最大值和最小值。
输入格式
第一行两个整数 n, m（1≤n≤50000，1≤m≤50000）
第二行 n 个整数，表示初始数组元素（绝对值≤100）
接下来 m 行，每行三个整数 l, r, k（1≤l≤r≤n，1≤k≤50）
输出格式
一行两个整数，分别为最终数组的最大值、最小值
样例输入
4 2
1 2 3 4
1 2 3
3 4 2样例输出
6 4参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 50010;
long long a[N], d[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
// 读入初始数组，构造差分
for(int i = 1; i <= n; i++)
{
cin >> a[i];
d[i] = a[i] - a[i-1];
}
// 区间修改
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
d[l] += k;
d[r+1] -= k;
}
// 还原数组并求最值
long long maxn = -1e18, minn = 1e18;
long long now = 0;
for(int i = 1; i <= n; i++)
{
now += d[i];
maxn = max(maxn, now);
minn = min(minn, now);
}
cout << maxn << " " << minn << endl;
return 0;
}
上一题
下一题