5236. 【NOIP2017模拟8.7A组】利普希茨

(File IO): input:lipschitz.in output:lipschitz.out

Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits

Description

Input

输入文件名为lipschitz.in。

第一行一个整数n。

接下来一行n个整数，描述序列A。

第三行一个数q 。

接下来q行，每行三个整数。其中第一个整数type表示操作的类型。 type=0对应修改操作， type=1对应查询操作。

Output

输出文件名为lipschitz.out。

对于每个查询，给出f(A[l..r]) 。

Sample Input

输入1：

6

90 50 78 0 96 20

6

0 1 35

1 1 4

0 1 67

0 4 11

0 3 96

1 3 5

输入2：

50

544 944 200 704 400 150 8 964 666 596 850 608 452 103 988 760 370 723 350 862 856 0 724 544 668 891 575 448 16 613 952 745 990 459 740 960 752 194 335 575 525 12 618 80 618 224 240 600 562 283

10

1 6 6

1 1 3

0 11 78279

0 33 42738

0 45 67270

1 1 26

1 19 24

1 37 39

1 8 13

0 7 64428

Sample Output

输出1：

78

85

输出2：

0

744

77683

856

558

77683

Data Constraint

对于30%的数据，n,q<=500

对于60%的数据，n,q<=5000

对于100%的数据，n,q<=100000,0<=ai,val<=10^9

题解

可以转化成坐标

对于每个点(x,y)，y表示Ax，先把公式列出来

f(A)=maxi<j⌈|Aj−Ai|j−i⌉

显然，对于任意两点，|Aj−Ai|j−i求出来的就是斜率

因此，只用找到斜率最大的就可以了

对于ABC三点，lAB的斜率比lAC大

对于ABD三点，lBC的斜率比lAD大

所以，在三点中，一定存在相邻的两点最优

因此f(A)=max|Ai+1−Ai|

用线段树维护一下Ai+1−Ai就行了

代码

#include<cstdio>

#include<algorithm>

#define N 100010

struct node{

    long maxx;

    node *lc,*rc;

}*head;

void init(node* &now)

{

    now=new node;

    now->maxx=0;

    now->lc=now->rc=NULL;

}

void build(long l,long r,node* &now=head)

{

    init(now);

    if(l!=r){

        long mid=(l+r)>>1;

        build(l,mid,now->lc);

        build(mid+1,r,now->rc);

    }

}

void change(long l,long r,long x,long key,node* &now=head)

{

    if(l==r)now->maxx=key;

    else{

        long mid=(l+r)>>1;

        if(x<=mid)

            change(l,mid,x,key,now->lc);

        else

            change(mid+1,r,x,key,now->rc);

        now->maxx=std::max(now->lc->maxx,now->rc->maxx);

    }

}

long query(long l,long r,long x,long y,node *now=head)

{

    if(x<=l&&r<=y)return now->maxx;

    else{

        long mid=(l+r)>>1,maxx=0;

        if(x<=mid)

            maxx=std::max(maxx,query(l,mid,x,y,now->lc));

        if(y>mid)

            maxx=std::max(maxx,query(mid+1,r,x,y,now->rc));

        return maxx;

    }

}

long a[N];

int main()

{   long n,m,i,x,y,z;

    freopen("lipschitz.in","r",stdin);

    freopen("lipschitz.out","w",stdout);

    scanf("%ld",&n);

    build(1,n);

    for(i=1;i<=n;i++){

        scanf("%ld",&a[i]);

        if(i!=1)

            change(1,n,i-1,abs(a[i-1]-a[i]));

    }

    change(1,n,n,a[n]);

    scanf("%ld",&m);

    for(i=1;i<=m;i++){

        scanf("%ld%ld%ld",&x,&y,&z);

        if(!x){

            a[y]=z;

            change(1,n,y-1,abs(a[y-1]-a[y]));

            change(1,n,y,abs(a[y]-a[y+1]));

        }else

            printf("%ld\n",query(1,n,y,z-1));

    }

    return 0;

}

巴特西

JZOJ 5236. 【NOIP2017模拟8.7A组】利普希茨