湛江网站建设公司,建设银行河北省分行官方网站,宝安中心是富人区吗,wordpress文章图片显示大图传送门:牛客
题目描述:
给出一个序列#xff0c;你的任务是求每次操作之后序列中 #xff08;a[j]-a[i]#xff09;/#xff08;j-i#xff09;【1ijn】的最大值。
操作次数有Q次#xff0c;每次操作需要将位子p处的数字变成y.
输入:
5
2 4 6 8 10
2
2 5
4…传送门:牛客
题目描述:
给出一个序列你的任务是求每次操作之后序列中 a[j]-a[i]/j-i【1ijn】的最大值。
操作次数有Q次每次操作需要将位子p处的数字变成y.
输入:
5
2 4 6 8 10
2
2 5
4 9
输出:
3.00
3.00对于本题,首先我们得分析出这道题的式子的巧妙之处才能动手
对于区间内任意的i,ji,ji,j,假设i,ji,ji,j直接没有夹杂其他的数字,那么此处我们的式子的值就是a[j]−a[i]a[j]-a[i]a[j]−a[i],假设我们的i,ji,ji,j之间存在a1,a2,a3,a4a1,a2,a3,a4a1,a2,a3,a4,此时我们的式子就可以表示为 (a[j]−a4a4−a3a3−a2a2−a1a1−a[i])/6(a[j]-a4a4-a3a3-a2a2-a1a1-a[i])/6(a[j]−a4a4−a3a3−a2a2−a1a1−a[i])/6,此时我们会显然的发现这个式子就是我们i,ji,ji,j之间的所有相邻的数字的差的和的平均值.对于这个平均值来说,显然取最大的差是我们的这个式子最大的时候. 那么此时这道题就变成了如何维护区间内相邻两个数的差的最大值
我们可以线段树来维护这个值.考虑使用mxmxmx来表示区间内相邻两个数的差的最大值 使用lnumlnumlnum来表示区间的左端点的数字,为了区间合并方便 使用rnumrnumrnum来表示区间的右端点的数字,为了区间合并方便
对于区间合并,我们会发现显然我们的大区间的mxmxmx有三种情况,1.左区间的mxmxmx 2.右区间的mxmxmx 3.有区间的lnumlnumlnum-左区间的rnumrnumrnum 三者取一个maxmaxmax维护即可
对于updateupdateupdate,queryqueryquery,简单的单点修改和区间查询,此处就不再赘述了
下面是具体的代码部分:
#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 maxn 200100
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r;int mx;int lnum,rnum;
}tree[maxn*4];
int n,m;int a[maxn];
void pushup(Segment_tree u,Segment_tree l,Segment_tree r) {u.ll.l;u.rr.r;u.lnuml.lnum;u.rnumr.rnum;u.mxmax(l.mx,r.mx);u.mxmax(u.mx,r.lnum-l.rnum);
}
void pushup(int rt) {pushup(tree[rt],tree[ls],tree[rs]);
}
void build(int l,int r,int rt) {tree[rt].ll;tree[rt].rr;tree[rt].mx-int_INF;if(lr) {tree[rt].lnumtree[rt].rnuma[l];return ;}int mid(lr)1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int v,int rt) {if(tree[rt].lpostree[rt].rpos) {tree[rt].lnumtree[rt].rnumv;return ;}int mid(tree[rt].ltree[rt].r)1;if(posmid) update(pos,v,ls);else update(pos,v,rs);pushup(rt);
}
int main() {while(scanf(%d,n)!EOF) {for(int i1;in;i) a[i]read();build(root);mread();for(int i1;im;i) {int posread(),vread();update(pos,v,1);printf(%.2lf\n,(double)tree[1].mx);}}return 0;
}
