题目描述
给出一个序列,你的任务是求每次操作之后序列中 (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;
}