本文共 2199 字，大约阅读时间需要 7 分钟。

链接：https://ac.nowcoder.com/acm/contest/3566/D

来源：牛客网

题目描述

小翔爱玩泰拉瑞亚 。 一天，他碰到了一幅地图。这幅地图可以分为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，相邻两数间用一个空格隔开。 输出描述: 一行一个整数，表示高度差的最大值。 输入 3 3 7 -2 -10 1 3 4 3 3 4 1 2 8

输出

21 题意：有n个数和m个区间操作，每次区间操作会减少一定的值，问你最终n个数里的最大值-最小值的差的最大值是多少？

分析：显然，一顿操作后最大值和最小值一定会在具体的某个位置，我们假设它在i位置，那么所有区间包含了i的操作都会使这个最小值越来越小，有可能会改变最大值，但是最大值要么一起减少，要么不变，对最终答案并无影响。所以可以得出有用的区间就是包含了i位置的区间，但是需要注意对于其他没有包含i的区间你要使用了之后将它变回原样，否则会影响最大值（最大值和最小值就不会一起减少了）。于是，可以先枚举每个位置i，假设i位置就是最小值，维护区间最大值，更新答案即可。

#include 
   
    using namespace std;typedef long long ll;const int maxn=2e5+1;ll h[maxn],ans=0;vector
    
     L[maxn],R[maxn];struct node{   	int l,r;	ll minn,maxx,lazy;}tree[maxn<<2];struct cxk{   	int l,r;	ll val;}s[maxn];bool cmp(const cxk &a,const cxk &b){   	return a.l
     
      
       >1;	 build(x<<1,l,mid);	 build(x<<1|1,mid+1,r);	 pushup(x);}void update(int x,int l,int r,ll val){   	if(l<=tree[x].l&&tree[x].r<=r)	{   		tree[x].maxx+=val;		tree[x].minn+=val;		tree[x].lazy+=val;		return ;	}	pushdown(x);	int mid=(tree[x].l+tree[x].r)>>1;	if(r<=mid) update(x<<1,l,r,val);	else if(l>mid) update(x<<1|1,l,r,val);	else update(x<<1,l,mid,val),update(x<<1|1,mid+1,r,val);	pushup(x);}ll query(int x,int l,int r,int op){   	if(l<=tree[x].l&&tree[x].r<=r)	{   		return op==1?tree[x].maxx:tree[x].minn;	}	pushdown(x);	int mid=(tree[x].l+tree[x].r)>>1;	if(r<=mid) return query(x<<1,l,r,op);	else if(l>mid) return query(x<<1|1,l,r,op);	else 	{   		if(op==1) return max(query(x<<1,l,mid,op),query(x<<1|1,mid+1,r,op));		else return min(query(x<<1,l,mid,op),query(x<<1|1,mid+1,r,op));	}}int main(){   	int n,m;	scanf("%d %d",&n,&m);	for(int i=1;i<=n;++i) scanf("%lld",&h[i]);	build(1,1,n);	for(int i=1;i<=m;++i) scanf("%d %d %lld",&s[i].l,&s[i].r,&s[i].val);	sort(s+1,s+1+m,cmp);	for(int i=1;i<=m;++i) L[s[i].l].push_back(i),R[s[i].r+1].push_back(i);	for(int i=1;i<=n;++i)	{   		for(int j=0;j