网站建设项目需求书,葫芦岛手机网站建设,如何做网站结构优化,网站的绝对路径怎么做传送门:牛客
题目描述:
小翔爱玩泰拉瑞亚 。
一天#xff0c;他碰到了一幅地图。这幅地图可以分为n列#xff0c;第i列的高度为Hi#xff0c;他认为这个地图不好看#xff0c;决定对它进行改造。
小翔又学会了m个魔法#xff0c;实施第i个魔法可以使地图的第Li列到第Ri列…传送门:牛客
题目描述:
小翔爱玩泰拉瑞亚 。
一天他碰到了一幅地图。这幅地图可以分为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刚开始看完这道题的时候,我感觉这道题没什么思路.感觉最难处理的方面是如何解决使用几个魔法的问题.也就是说刚开始我不知道对于一个点来说,使用什么关于这个点的魔法是最优的.然后看了看官方的简单题解之后恍然大悟.
可以说这道题有点诈骗题的感觉.我们可以有一个结论,对于一个点来说,直接使用所有能对这个点产生影响的魔法是最优的.
接下来来证明一下这结论,对于目前的点iii来说,我们此时使用一个魔法[l,r][l,r][l,r],这个魔法影响了iii点,我们此时假设iii点为minminmin值点,那么此时对于区间外的一个maxmaxmax点来说,此时我们的魔法可能影响这个maxmaxmax点,也可能不影响这个maxmaxmax点,如果我们此时的魔法不影响这个maxmaxmax点,那么显然我们现在minminmin变小了,maxmaxmax不变是最优的;如果此时我们的魔法影响了这个maxmaxmax点,那么对于此时我们的max−minmax-minmax−min来说,此时的值是不变的.这是可能有人会有疑问了,此时的魔法可能影响我们此时的maxmaxmax不再是maxmaxmax啊?确实是这样的,但是我们可以在魔法使用过后重新求一个区间的maxmaxmax,如果这个maxmaxmax跟之前的maxmaxmax一样的话,此时变成了第一种情况,如果不一样,此时我们的新的maxmaxmax显然因为这次的魔法导致新的max-min超过了之前的max-min,此时我们的贡献依旧因为魔法变的更为优秀了.
所以无论魔法对其他点影响如何,只要使用所有能对这个点产生影响的魔法就是最优的.
只要我们枚举所有的点和对于该点能产生影响的魔法(枚举最小值),然后用线段树来维护区间的最大值即可.对于每一个魔法区间,我们先进行一个排序,这样就可以随着点的枚举而逐一加入魔法区间的影响了.对于每一个使用的魔法,我们都把它扔进一个小根堆(以坐标为关键字),然后此时我们判断一下有无失效即可
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000000
const double eps1e-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.ll.l;u.rr.r;u.lazy0;u.mnmin(l.mn,r.mn);u.mxmax(l.mx,r.mx);return u;
}
int n,m;int a[maxn];
void build(int l,int r,int rt) {tree[rt].ll;tree[rt].rr;tree[rt].mnint_INF;tree[rt].mx-int_INF;if(lr) {tree[rt].mxtree[rt].mna[l];return ;}int mid(lr)1;build(lson);build(rson);tree[rt]tree[ls]tree[rs];
}
void change(int rt,int v) {tree[rt].mnv;tree[rt].mxv;tree[rt].lazyv;
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy0;
}
void update(int l,int r,int v,int rt) {if(tree[rt].lltree[rt].rr) {change(rt,v);return ;}if(tree[rt].lazy!0) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) update(l,r,v,ls);else if(lmid) update(l,r,v,rs);else update(l,mid,v,ls),update(mid1,r,v,rs);tree[rt]tree[ls]tree[rs];
}
Segment_tree query(int l,int r,int rt) {if(tree[rt].lltree[rt].rr) {return tree[rt];}if(tree[rt].lazy!0) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) return query(l,r,ls);else if(lmid) return query(l,r,rs);else return query(l,mid,ls)query(mid1,r,rs);
}
struct Magic {int l,r,num;
}magic[maxn];
bool cmp(Magic aa,Magic bb) {if(aa.l!bb.l) return aa.lbb.l;else return aa.rbb.r;
}
struct heapnode{int l,r,num;bool operator (const heapnode rhs) const {return rrhs.r;}
};
signed main() {nread();mread();for(int i1;in;i) a[i]read();build(root);for(int i1;im;i) {magic[i].lread();magic[i].rread();magic[i].numread();}sort(magic1,magicm1,cmp);priority_queueheapnodeq;int ans-int_INF;int pos1;for(int i1;in;i) {while(posmmagic[pos].li) {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().ri) {update(q.top().l,q.top().r,q.top().num,1);q.pop();}ansmax(ans,query(1,n,1).mx-query(1,n,1).mn);}coutansendl;return 0;
}
