P11790 焚风现象
【题目来源】
洛谷：[P11790 JOI 2017 Final] 焚风现象 / Foehn Phenomena - 洛谷
【题目描述】
你知道 \(N+1\) 个地点的海拔 \(A_i\)，编号为 \(0 \dots N\)，有风从 \(0\) 吹向 \(N\)，想让你求出地点 \(N\) 的风的温度，保证 \(A_0=0\)。
规则：
- 如果 \(A_i=A_{i+1}\)，风的温度不变。
- 如果 \(A_i>A_{i+1}\)，由于海拔降低，风的温度会上升 \((A_i-A_{i+1})\times T\) 度。
- 如果 \(A_i<A_{i+1}\)，由于海拔升高，风的温度会下降 \((A_{i+1}-A_i)\times S\) 度。
【输入】
- 第一行输入包括四个被空格隔开的整数 \(N,Q,S,T\)。这表示 JOI 先生在地点 \(N\) 有一所房子，有 \(Q\) 次地壳运动，海拔每上升 \(1\) 米的话，风的温度会降低 \(S\) 度，海拔每下降一米的话,风的温度会上升 \(T\) 度。
- 接下来的 \(N+1\) 行中第 \(i\) 行 \((1\leq i\leq N+1)\) 包含一个整数 \(A_{i-1}\)，表示地壳运动前地点 \(i-1\) 的海拔高度。
- 接下来的 \(Q\) 行中第 \(j\) 行 \((1\leq j\leq Q)\) 包括三个被空格隔开的整数 \(L_j,R_j,X_j\)，这表示第 \(j\) 天地壳运动使地点 \(L_j\) 到地点 \(R_j\) 中这些地点的海拔变化了 \(X_j\)。
【输出】
输出 \(Q\) 行，第 \(j\) 行的输出代表第 \(j\) 天地壳运动后 JOI 先生家的风的温度。
（即 \(N\) 位置的风的温度。）
【输入样例】
3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5
【输出样例】
-5
-7
-13
-13
-18
【算法标签】
《洛谷 P11790 焚风现象》 #线段树# #差分# #JOI（日本）# #2017#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long longint n, q, s, t; // n: 数据点数，q: 操作次数，s: 上升惩罚系数，t: 下降奖励系数
int a[200005], d[200005], ans; // a: 原始数据，d: 差分数组，ans: 当前总花费// 根据差分值计算温度变化的花费
int change(int p)
{if (p > 0) // 如果温度升高{return -1 * (p * s); // 花费为温度升高度数乘以s（花费为负值，表示消耗）}else // 如果温度降低{return (-1 * p) * t; // 花费为温度降低度数乘以t（花费为正值，表示奖励）}
}signed main()
{cin >> n >> q >> s >> t; // 读入n, q, s, tcin >> a[0]; // 读入初始温度// 初始化差分数组并计算初始总花费for (int i = 1; i <= n; i++){cin >> a[i]; // 读入第i个温度d[i] = a[i] - a[i - 1]; // 计算差分ans += change(d[i]); // 计算初始总花费}// 处理q次操作for (int i = 1; i <= q; i++){int l, r, x;cin >> l >> r >> x; // 读入操作区间和变化值// 更新左边界差分ans -= change(d[l]); // 先减去原来的贡献d[l] += x; // 更新差分ans += change(d[l]); // 加上新的贡献// 更新右边界+1的差分（如果r+1不超出范围）if (r < n){ans -= change(d[r + 1]); // 先减去原来的贡献d[r + 1] -= x; // 更新差分ans += change(d[r + 1]); // 加上新的贡献}cout << ans << endl; // 输出当前总花费}return 0;
}
【运行结果】
3 5 1 2
0
4
1
8
1 2 2
-5
1 1 -2
-7
2 3 5
-13
1 2 -1
-13
1 3 5
-18