链接：https://ac.nowcoder.com/acm/contest/3566/D
来源：牛客网

---

小翔和泰拉瑞亚

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld

题目描述

小翔爱玩泰拉瑞亚 。
一天，他碰到了一幅地图。这幅地图可以分为n列，第i列的高度为Hi，他认为这个地图不好看，决定对它进行改造。
小翔又学会了m个魔法，实施第i个魔法可以使地图的第Li列到第Ri列每一列的高度减少Wi，每个魔法只能实施一次，魔法的区间可能相交或包含。
小翔认为，一幅地图中最高的一列与最低的一列的高度差越大，这幅地图就越美观。
小翔可以选择m个魔法中的任意一些魔法来实施，使得地图尽量美观。但是他不知道该如何选择魔法，于是他找到了你。请你求出所有可行方案中，高度差的最大值。
对于100%的数据，满足1≤n,m≤200000,-109≤Hi≤109,1≤Wi≤109,1≤Li≤Ri≤n。

输入描述:

输入文件的第一行包含两个整数n,m。
输入的第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为Hi。
接下来的m行，每行包含3个整数，分别是Li,Ri,Wi，相邻两数间用一个空格隔开。

输出描述:

一行一个整数，表示高度差的最大值。

示例1

输入
复制

3 3 7 -2 -10 1 3 4 3 3 4 1 2 8

输出
复制

21

思路：

区间更新，线段树去维护。
极差最大，值只减小，考虑固定最小值，然后求整个区间的最大值。
假设i位置上的值是最小值，那么覆盖了i的区间都可以对i位置上的值变小产生贡献，即[l,r],l<=i&&r>=i的区间能够让假设位置的最小值变小（l<i&&r>=i的在i之前已经使用了但是没有被撤销，此时只需使用l=i的区间）。那么此时应该把这些区间都使用一下，然后询问一下整个区间的最大值。
按上述假设做的正确性很容易证明：如果最大值在使用过的区间里面，因为是同时更新，对结果没有影响；如果不在使用的区间里面，那更明显，最小值变小了，最大值没有受到影响，极差肯定变大！
此时要考虑i+1为最小值了，之前用过的区间对i+1位置没有贡献的要撤销，因为可能影响到最大值。之前使用的区间[l,r]对i+1没有贡献的条件是：r<i+1。即在每次使用i+1之前把r=i的区间撤销。
时间复杂度分析：
影响时间复杂度的是区间操作（不能单纯看循环来定时间复杂度）。
对于区间操作，每个区间最多操作2次，每次操作复杂度为logn,
共m个区间，所以时间复杂度为：mlogn

AC代码:

#include <bits/stdc++.h> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define ls rt<<1 #define rs rt<<1|1 using namespace std; typedef long long LL; const LL N = 2e5+5; const LL INF = 0x3f3f3f3f3f3f3f3f; int a[N]; struct Node {LL minx,maxx;LL tag; }node[N<<2]; struct PII {int l,r,v; }; vector<PII> L[N],R[N]; inline void push_up(int rt) {node[rt].minx = min(node[ls].minx,node[rs].minx);node[rt].maxx = max(node[ls].maxx,node[rs].maxx);return; } void build_tree(int rt,int l,int r) {node[rt].tag = 0;if(l == r){node[rt].minx = a[l];node[rt].maxx = a[l];return;}int mid = (l + r) >> 1;build_tree(lson);build_tree(rson);push_up(rt); } inline void push_down(int rt) {if(node[rt].tag){//认真思考，不要少更新了需要维护的值！node[ls].minx += node[rt].tag;node[ls].maxx += node[rt].tag;node[ls].tag += node[rt].tag;node[rs].minx += node[rt].tag;node[rs].maxx += node[rt].tag;node[rs].tag += node[rt].tag;node[rt].tag = 0;}return; } void update_range(int L,int R,int v,int rt,int l,int r) {if(L <= l && r <= R){node[rt].minx += v;node[rt].maxx += v;node[rt].tag += v;return;}push_down(rt);int mid = (l + r) >> 1;if(L <= mid)update_range(L,R,v,lson);if(R > mid)update_range(L,R,v,rson);push_up(rt); } int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}build_tree(1,1,n);PII p;while(m--){scanf("%d%d%d",&p.l,&p.r,&p.v);L[p.l].push_back(p);R[p.r].push_back(p);}LL ans = node[1].maxx - node[1].minx;for(int i = 1; i <= n; i++){int lSize = L[i].size();int rSize = R[i].size();for(int j = 0; j < lSize; j++){update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);}ans = max(ans,node[1].maxx - node[1].minx);for(int j = 0; j < rSize; j++){update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);}}printf("%lld\n",ans);return 0; }

另一种写法：

#include <bits/stdc++.h> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define ls rt<<1 #define rs rt<<1|1 using namespace std; typedef long long LL; const LL N = 2e5+5; const LL INF = 1e18; int a[N]; struct Node {LL minx,maxx;LL tag; }node[N<<2]; struct PII {int l,r,v; }; vector<PII> L[N],R[N]; inline void push_up(int rt) {node[rt].minx = min(node[ls].minx,node[rs].minx);node[rt].maxx = max(node[ls].maxx,node[rs].maxx); } void build(int rt,int l,int r) {node[rt].tag = 0;if(l == r){node[rt].minx = a[l];node[rt].maxx = a[l];return;}int mid = (l + r) >> 1;build(lson);build(rson);push_up(rt); } inline void push_down(int rt) {if(node[rt].tag){node[ls].minx += node[rt].tag;node[ls].maxx += node[rt].tag;node[ls].tag += node[rt].tag;node[rs].minx += node[rt].tag;node[rs].maxx += node[rt].tag;node[rs].tag += node[rt].tag;node[rt].tag = 0;}return; } void update_range(int L,int R,int v,int rt,int l,int r) {if(L <= l && r <= R){node[rt].minx += v;node[rt].maxx += v;node[rt].tag += v;return;}push_down(rt);int mid = (l + r) >> 1;if(L <= mid)update_range(L,R,v,lson);if(R > mid)update_range(L,R,v,rson);push_up(rt); }LL query_min(int L,int R,int rt,int l,int r) {if(L <= l && r <= R){return node[rt].minx;}push_down(rt);int mid = (l + r) >> 1;LL res = INF;if(L <= mid)return min(res,query_min(L,R,lson));if(R > mid)return min(res,query_min(L,R,rson));return res; } LL query_max(int L,int R,int rt,int l,int r) {if(L <= l && r <= R){return node[rt].maxx;}push_down(rt);int mid = (l + r) >> 1;LL res = -INF;if(L <= mid)return max(res,query_max(L,R,lson));if(R > mid)return max(res,query_max(L,R,rson));return res; } int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}build(1,1,n);PII p;while(m--){scanf("%d%d%d",&p.l,&p.r,&p.v);L[p.l].push_back(p);R[p.r].push_back(p);}LL ans = -INF;for(int i = 1; i <= n; i++){int lSize = L[i].size();int rSize = R[i].size();for(int j = 0; j < lSize; j++){update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);}/*这里去query_max(1,n,1,1,n)会测试样例的5%会时间超限，因为update_range的时候，更新结果会push_up上去,此时完全可以不写query（我写是因为很久没写了，巩固一下），node[1]上的最值即为需要的值。*/ans = max(ans,node[1].maxx-query_min(i,i,1,1,n));for(int j = 0; j < rSize; j++){update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);}}printf("%lld\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的小翔和泰拉瑞亚（线段树+思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。