题目描述
给出一个序列，你的任务是求每次操作之后序列中 （a[j]-a[i]）/（j-i）【1<=i<j<=n】的最大值。
操作次数有Q次，每次操作需要将位子p处的数字变成y.
输入描述:
本题包含多组输入，每组输入第一行一个数字n，表示序列的长度。
然后接下来一行输入n个数，表示原先序列的样子。
再接下来一行一个数字Q，表示需要进行的操作的次数。
最后Q行每行两个元素p，y，表示本操作需要将位子p处的数字变成y.
数据范围：
3<=n<=200000
1<=Q<=200000
-1000000000<=a[i]<=1000000000
输出描述:
每组数据输出Q行，每行输出一个浮点数，保留两位小数，表示所求的最大值。
示例1
输入
复制
5
2 4 6 8 10
2
2 5
4 9
输出
复制
3.00
3.00
说明
第一次操作之后的序列变成：2 5 6 8 10
第二次操作之后的序列变成：2 5 6 9 10

我们可以看出式子的几何意义即表示线段的斜率。

然后我们通过画图可以得知，斜率最大值，必然是出现在相邻的两项之间，不然我们随便取一点与两个端点相连，必然能产生更大的斜率。

所以我们维护以每个点开始，与后面那个点的斜率即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5;
int n,q,a[N];
struct node{
	int l,r,mx;
}t[N<<2];
inline void push_up(int p){
	t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r)	return void(t[p].mx=a[l+1]-a[l]);
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int x,int v){
	if(t[p].l==t[p].r){
		t[p].mx=v; return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x,v);
	else	change(p<<1|1,x,v);
	push_up(p);
}
signed main(){
	while(cin>>n){
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
		cin>>q; build(1,1,n-1);
		while(q--){
			int p,y;	scanf("%d %d",&p,&y);	a[p]=y;
			if(p!=n)	change(1,p,a[p+1]-y);	
			if(p!=1)	change(1,p-1,a[p]-a[p-1]);
			printf("%d.00\n",t[1].mx);
		}
	}
	return 0;
}