Description

Input

輸入文件名為lipschitz.in。
第一行一個(gè)整數(shù)n。
接下來一行n個(gè)整數(shù)，描述序列A。
第三行一個(gè)數(shù)q 。
接下來q行，每行三個(gè)整數(shù)。其中第一個(gè)整數(shù)type表示操作的類型。 type=0對(duì)應(yīng)修改操作， type=1對(duì)應(yīng)查詢操作。

Output

輸出文件名為lipschitz.out。
對(duì)于每個(gè)查詢，給出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

對(duì)于30%的數(shù)據(jù)，n,q<=500
對(duì)于60%的數(shù)據(jù)，n,q<=5000
對(duì)于100%的數(shù)據(jù)，n,q<=100000,0<=ai,val<=10^9

Solution

• 解決本題，關(guān)鍵是發(fā)現(xiàn)選取 i，j 的一個(gè)性質(zhì)：

  i+1=j

• 即只會(huì)選取 相鄰的兩個(gè)數(shù) 作為答案，為什么呢?

• 設(shè)三個(gè)數(shù)：a，b，c（a<b<c） ，則選 a和c 不會(huì)比 選a和b 更差。

• 因?yàn)橛?#xff1a;c?a2≤b?a 或 c?a2≤c?b（兩式至少有一式成立，當(dāng)b為a、c的平均數(shù)時(shí)等式成立）

• 那么將這 N 個(gè)數(shù)相鄰的兩兩作差（絕對(duì)值），則產(chǎn)生 N-1 個(gè)差值，用線段樹維護(hù)最大值即可。

• 對(duì)于修改操作，只需單點(diǎn)修改相鄰的兩個(gè)點(diǎn)即可維護(hù)，時(shí)間復(fù)雜度為 O(NlogN) 。

Code

#include<cstdio> #include<cmath> using namespace std; const int N=100001; int a[N],f[N<<2]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline void build(int v,int l,int r) {if(l==r){f[v]=abs(a[l]-a[l+1]);return;}int mid=(l+r)>>1;build(v<<1,l,mid);build(v<<1|1,mid+1,r);f[v]=max(f[v<<1],f[v<<1|1]); } inline void change(int v,int l,int r,int x) {if(l==r){f[v]=abs(a[l]-a[l+1]);return;}int mid=(l+r)>>1;if(x<=mid) change(v<<1,l,mid,x); else change(v<<1|1,mid+1,r,x);f[v]=max(f[v<<1],f[v<<1|1]); } inline int query(int v,int l,int r,int x,int y) {if(x>y) return 0;if(l>=x && r<=y) return f[v];int mid=(l+r)>>1;if(y<=mid) return query(v<<1,l,mid,x,y);if(x>mid) return query(v<<1|1,mid+1,r,x,y);return max(query(v<<1,l,mid,x,mid),query(v<<1|1,mid+1,r,mid+1,y)); } int main() {int n=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n-1);int q=read();while(q--){int type=read(),l=read(),r=read();if(!type){a[l]=r;change(1,1,n-1,l);if(l>1) change(1,1,n-1,l-1);}else printf("%d\n",query(1,1,n-1,l,r-1));}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5236. 【NOIP2017模拟8.7A组】利普希茨的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。