NC 54586 线段树

题意

传送门 NC 54586 小翔和泰拉瑞亚

题解

考虑 $i,j$ 为答案对应的索引，设 $H_i>H_j$，则实施的魔法分 $3$ 种情况：$i,j\in [L_i,R_i]$；$i\notin [L_i,R_i],j\in [L_i,R_i]$；$i\in [L_i,R_i],j\notin [L_i,R_i]$。显然前两种情况使 $H_i-H_j$ 保持原值或增大，那么枚举每一个索引 $i$，实施所有覆盖 $i$ 的魔法，更新答案即可。

#include <bits/stdc++.h> using namespace std; #define maxn 200005 #define sg_size (1 << 19) - 1 typedef long long ll; struct intv{int x, w;}; struct node{ll mx, mn;} sg[sg_size]; int n, m, h[maxn]; ll lz[sg_size]; vector<intv> L[maxn], R[maxn]; inline void pushup(int k, int chl, int chr) { sg[k].mx = max(sg[chl].mx, sg[chr].mx); sg[k].mn = min(sg[chl].mn, sg[chr].mn); } void init(int k, int l, int r) { if (r - l == 1) { sg[k] = node{h[l], h[l]}; } else { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; init(chl, l, m); init(chr, m, r); pushup(k, chl, chr); } } inline void pushdown(int k, int chl, int chr) { if (lz[k] != 0) { sg[chl].mx += lz[k], sg[chl].mn += lz[k]; sg[chr].mx += lz[k], sg[chr].mn += lz[k]; lz[chl] += lz[k], lz[chr] += lz[k]; lz[k] = 0; } } void update(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { sg[k].mx += x, sg[k].mn += x; lz[k] += x; } else if (l < b && a < r) { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; pushdown(k, chl, chr); update(a, b, x, chl, l, m); update(a, b, x, chr, m, r); pushup(k, chl, chr); } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", h + i); } while (m--) { int l, r, w; scanf("%d%d%d", &l, &r, &w); --l, --r; L[l].push_back(intv{r, w}); R[r].push_back(intv{l, w}); } init(0, 0, n); ll res = sg[0].mx - sg[0].mn; for (int i = 0; i < n; i++) { for (auto it : L[i]) { update(i, it.x + 1, -it.w, 0, 0, n); } res = max(res, sg[0].mx - sg[0].mn); for (auto it : R[i]) { update(it.x, i + 1, it.w, 0, 0, n); } } printf("%lld\n", res); return 0; }