刷题记录:牛客NC54586小翔和泰拉瑞亚

传送门:牛客

题目描述:

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

刚开始看完这道题的时候,我感觉这道题没什么思路.感觉最难处理的方面是如何解决使用几个魔法的问题.也就是说刚开始我不知道对于一个点来说,使用什么关于这个点的魔法是最优的.然后看了看官方的简单题解之后恍然大悟.

可以说这道题有点诈骗题的感觉.我们可以有一个结论,对于一个点来说,直接使用所有能对这个点产生影响的魔法是最优的.

接下来来证明一下这结论,对于目前的点$i$来说,我们此时使用一个魔法$[l,r]$,这个魔法影响了$i$点,我们此时假设$i$点为$min$值点,那么此时对于区间外的一个$max$点来说,此时我们的魔法可能影响这个$max$点,也可能不影响这个$max$点,如果我们此时的魔法不影响这个$max$点,那么显然我们现在$min$变小了,$max$不变是最优的;如果此时我们的魔法影响了这个$max$点,那么对于此时我们的$max-min$来说,此时的值是不变的.这是可能有人会有疑问了,此时的魔法可能影响我们此时的$max$不再是$max$啊?确实是这样的,但是我们可以在魔法使用过后重新求一个区间的$max$,如果这个$max$跟之前的$max$一样的话,此时变成了第一种情况,如果不一样,此时我们的新的$max$显然因为这次的魔法导致新的max-min超过了之前的max-min,此时我们的贡献依旧因为魔法变的更为优秀了.

所以无论魔法对其他点影响如何,只要使用所有能对这个点产生影响的魔法就是最优的.

只要我们枚举所有的点和对于该点能产生影响的魔法(枚举最小值),然后用线段树来维护区间的最大值即可.对于每一个魔法区间,我们先进行一个排序,这样就可以随着点的枚举而逐一加入魔法区间的影响了.对于每一个使用的魔法,我们都把它扔进一个小根堆(以坐标为关键字),然后此时我们判断一下有无失效即可

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{
	int l,r,mx,mn,lazy;
}tree[maxn*4];
Segment_tree operator + (Segment_tree l,Segment_tree r) {
	Segment_tree u;u.l=l.l;u.r=r.r;u.lazy=0;
	u.mn=min(l.mn,r.mn);
	u.mx=max(l.mx,r.mx);
	return u;
}
int n,m;int a[maxn];
void build(int l,int r,int rt) {
	tree[rt].l=l;tree[rt].r=r;tree[rt].mn=int_INF;tree[rt].mx=-int_INF;
	if(l==r) {
		tree[rt].mx=tree[rt].mn=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	tree[rt]=tree[ls]+tree[rs];
}
void change(int rt,int v) {
	tree[rt].mn+=v;tree[rt].mx+=v;
	tree[rt].lazy+=v;
}
void pushdown(int rt) {
	change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);
	tree[rt].lazy=0;
}
void update(int l,int r,int v,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		change(rt,v);
		return ;
	}
	if(tree[rt].lazy!=0) pushdown(rt);
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) update(l,r,v,ls);
	else if(l>mid) update(l,r,v,rs);
	else update(l,mid,v,ls),update(mid+1,r,v,rs);
	tree[rt]=tree[ls]+tree[rs];
}
Segment_tree query(int l,int r,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		return tree[rt];
	}
	if(tree[rt].lazy!=0) pushdown(rt);
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) return query(l,r,ls);
	else if(l>mid) return query(l,r,rs);
	else return query(l,mid,ls)+query(mid+1,r,rs);
}
struct Magic {
	int l,r,num;
}magic[maxn];
bool cmp(Magic aa,Magic bb) {
	if(aa.l!=bb.l) return aa.l<bb.l;
	else return aa.r<bb.r;
}
struct heapnode{
	int l,r,num;
	bool operator <(const heapnode &rhs) const {
		return r>rhs.r;
	}
};
signed main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(root);
	for(int i=1;i<=m;i++) {
		magic[i].l=read();magic[i].r=read();magic[i].num=read();
	}
	sort(magic+1,magic+m+1,cmp);
	priority_queue<heapnode>q;
	int ans=-int_INF;int pos=1;
	for(int i=1;i<=n;i++) {
		while(pos<=m&&magic[pos].l<=i) {
			update(magic[pos].l,magic[pos].r,-magic[pos].num,1);
			q.push({magic[pos].l,magic[pos].r,magic[pos].num});
			pos++;
		}
		while(!q.empty()&&q.top().r<i) {
			update(q.top().l,q.top().r,q.top().num,1);
			q.pop();
		}
		ans=max(ans,query(1,n,1).mx-query(1,n,1).mn);
	}
	cout<<ans<<endl;
	return 0;
}