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$表示$A_x$，先把公式列出来

$$f(A)=max_{i<j} \lceil \dfrac{|A_j-A_i|}{j-i} \rceil$$

显然，对于任意两点，$\dfrac{|A_j-A_i|}{j-i}$求出来的就是斜率
因此，只用找到斜率最大的就可以了

对于$ABC$三点，$l_{AB}$的斜率比$l_{AC}$大
对于$ABD$三点，$l_{BC}$的斜率比$l_{AD}$大

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

因此$f(A)=max|A_{i+1}-A_{i}|$
用线段树维护一下$A_{i+1}-A_{i}$就行了

代码

#include<cstdio>
#include<algorithm>
#define N 100010struct 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);elsechange(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]));}elseprintf("%ld\n",query(1,n,y,z-1));}return 0;
}