刷题记录:牛客NC14402求最大值

传送门:牛客

题目描述:

给出一个序列，你的任务是求每次操作之后序列中 （a[j]-a[i]）/（j-i）【1<=i<j<=n】的最大值。
操作次数有Q次，每次操作需要将位子p处的数字变成y.
输入:
5
2 4 6 8 10
2
2 5
4 9
输出:
3.00
3.00

对于本题,首先我们得分析出这道题的式子的巧妙之处才能动手

对于区间内任意的$i,j$,假设$i,j$直接没有夹杂其他的数字,那么此处我们的式子的值就是$a[j]-a[i]$,假设我们的$i,j$之间存在$a1,a2,a3,a4$,此时我们的式子就可以表示为
$(a[j]-a4+a4-a3+a3-a2+a2-a1+a1-a[i])/6$,此时我们会显然的发现这个式子就是我们$i,j$之间的所有相邻的数字的差的和的平均值.对于这个平均值来说,显然取最大的差是我们的这个式子最大的时候.
那么此时这道题就变成了如何维护区间内相邻两个数的差的最大值

我们可以线段树来维护这个值.考虑使用$mx$来表示区间内相邻两个数的差的最大值
使用$lnum$来表示区间的左端点的数字,为了区间合并方便
使用$rnum$来表示区间的右端点的数字,为了区间合并方便

对于区间合并,我们会发现显然我们的大区间的$mx$有三种情况,1.左区间的$mx$ 2.右区间的$mx$ 3.有区间的$lnum$-左区间的$rnum$ 三者取一个$max$维护即可

对于$update$,$query$,简单的单点修改和区间查询,此处就不再赘述了

下面是具体的代码部分:

#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 maxn 200100
const double eps=1e-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.l=l.l;u.r=r.r;
	u.lnum=l.lnum;u.rnum=r.rnum;
	u.mx=max(l.mx,r.mx);
	u.mx=max(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].l=l;tree[rt].r=r;tree[rt].mx=-int_INF;
	if(l==r) {
		tree[rt].lnum=tree[rt].rnum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	pushup(rt);
}
void update(int pos,int v,int rt) {
	if(tree[rt].l==pos&&tree[rt].r==pos) {
		tree[rt].lnum=tree[rt].rnum=v;
		return ;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(pos<=mid) update(pos,v,ls);
	else update(pos,v,rs);
	pushup(rt);
}
int main() {
	while(scanf("%d",&n)!=EOF) {
		for(int i=1;i<=n;i++) a[i]=read();
		build(root);
		m=read();
		for(int i=1;i<=m;i++) {
			int pos=read(),v=read();
			update(pos,v,1);
			printf("%.2lf\n",(double)tree[1].mx);
		}
	}
	return 0;
}