题目描述
给出一个序列,你的任务是求每次操作之后序列中 (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
第一点 昵题其实唔用开long long
第二点 最大值一定系相邻嘅两点
证明:1.只需考虑递增序列
2.将这些点形象与坐标系,(a[j]-a[i])/(j-i)就是斜率,画图就知了
talk is cheap,show you the code
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=2e5+5; int maxx[maxn<<2],ln[maxn<<2],rn[maxn<<2]; int a[maxn]; int ans=0; void pushup(int rt,int l,int r) { maxx[rt]=max(maxx[rt<<1],max(maxx[rt<<1|1],ln[rt<<1|1]-rn[rt<<1])); ln[rt]=ln[rt<<1],rn[rt]=rn[rt<<1|1]; } void build(int rt,int l,int r) { if(l==r) { ln[rt]=a[l]; rn[rt]=a[r]; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt,l,r); } void update(int rt,int l,int r,int pos,int x) { if(l>pos||r<pos)return; if(l==r&&l==pos) { ln[rt]=x; rn[rt]=x; return; } int mid=(l+r)>>1; update(rt<<1,l,mid,pos,x); update(rt<<1|1,mid+1,r,pos,x); pushup(rt,l,r); } int main() { int n; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof a); memset(maxx,-0x3f3f3f3f,sizeof maxx); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } int m; scanf("%d",&m); build(1,1,n); for(int i=1; i<=m; i++) { int pos; int x; scanf("%d%d",&pos,&x); update(1,1,n,pos,x); ans=maxx[1]; double res; res=(double)ans; printf("%.2f\n",res); } } return 0; }