0x00 题目翻译

一个长度为 nn 的序列，求出对于所有 1≤l≤r≤n1\le l\le r\le n，

max⁡(al,al+1,…,ar)−min⁡(al,al+1,…,ar)−(r−l)\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r - l)

的最大值。

每一组数据，先输出这个序列的答案，之后 qq 行修改操作，每行的 p x 表示把 apa_p 修改为 xx，修改对之后的所有操作有影响，每一次修改后，输出新序列的答案。

0x01 解题思路

解题的关键就是对这个式子进行变形：

max⁡(al,al+1,…,ar)−min⁡(al,al+1,…,ar)−(r−l)\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r - l)

首先观察到，选取的最大最小值一定在区间的两端（如果不在两端，那么可以去掉左右无用的部分，答案一定更优），于是式子变为：

∣al−ar∣−(r−l)\vert a_l-a_r\vert- (r - l)

绝对值意味着分类讨论，因为这里要求的是最大值，所以可以简单地去掉绝对值后对两种情况取最值：

max⁡{al−ar−(r−l),ar−al−(r−l)}\max\{a_l-a_r- (r - l),a_r-a_l- (r - l)\}

发现 (r−1)(r-1) 是一个和序列无关的整体，这并不好处理，可以想到合并到序列（我是看了题解才想到的）：

max⁡{(al+l)−(ar+r),(ar−r)−(al−l)}\max\{(a_l+l)-(a_r+r),(a_r-r)-(a_l-l)\}

这样就可以使 (l−r)(l-r) 和序列成为一个整体，为了方便表示和处理，令 xi=ai+ix_i=a_i+i，yi=ai−iy_i=a_i-i，于是变为：

max⁡{xl−xr,yr−yl}\max\{x_l-x_r,y_r-y_l\}

这个时候就可以开始求答案了。

看到区间和修改，想到了线段树和区间DP，可以尝试结合这两者解决问题。

首先，对于题目的修改，想到用线段树去维护 xx 和 yy 两个序列，然后想怎样在线段树的合并（建树）中完成答案的求解。

线段树在建立的过程中不断合并左右两个子区间，求解也是类似的，每一次维护 ans1=xl−xrans_1=x_l-x_r，ans2=yr−ylans_2=y_r-y_l，结果就是 max⁡{ans1,ans2}\max\{ans_1,ans_2\}，但还没有这么简单，接下来对区间进行讨论：

  • 答案出现在左区间，直接取出计算完的数值；
  • 答案出现在右区间，直接取出计算完的数值；
  • 答案取自左区间和右区间，计算新的答案。

得出方程（符号表示有点混乱，具体看代码）：

ans1now=max⁡{ans1l,ans1r,xlmax−xrmax}ans2now=max⁡{ans2l,ans2r,yrmax−y2max}ans_{1_\text{now}}=\max\{ans_{1_l},ans_{1_r},x_{l_\text{max}}-x_{r_\text{max}}\} \\ ans_{2_\text{now}}=\max\{ans_{2_l},ans_{2_r},y_{r_\text{max}}-y_{2_\text{max}}\}

在线段树的 pushup 中完成计算就可以了。

0x02 算法实现

单点修改+区间查询，有不带懒标记的线段树直接实现即可。

0x03 程序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct SegmentTree{
	struct data{
		int X,Y;
		//X:-i Y:+i
	};
	data dat[200005];
	struct node{
		int l,r,minX,minY,maxX,maxY,ansA,ansB;
	};
	node t[4*200005];
	void pushup(int x){
		t[x].minX=min(t[x<<1].minX,t[x<<1|1].minX);
		t[x].minY=min(t[x<<1].minY,t[x<<1|1].minY);
		t[x].maxX=max(t[x<<1].maxX,t[x<<1|1].maxX);
		t[x].maxY=max(t[x<<1].maxY,t[x<<1|1].maxY);
		t[x].ansA=max({t[x<<1].ansA,t[x<<1|1].ansA,t[x<<1|1].maxX-t[x<<1].minX});
		t[x].ansB=max({t[x<<1].ansB,t[x<<1|1].ansB,t[x<<1].maxY-t[x<<1|1].minY});
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r;
		if(l==r){
			t[x].minX=t[x].maxX=dat[l].X;
			t[x].minY=t[x].maxY=dat[l].Y;
			t[x].ansA=t[x].ansB=0;
			return;
		}
		int mid=l+r>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		pushup(x);
	}
	void update(int x,int X){
		int l=t[x].l,r=t[x].r;
		if(l==r){
			t[x].minX=t[x].maxX=dat[l].X;
			t[x].minY=t[x].maxY=dat[l].Y;
			return;
		}
		int mid=l+r>>1;
		if(X<=mid)update(x<<1,X);
		else update(x<<1|1,X);
		pushup(x);
	}
	int query(){
		return max(t[1].ansA,t[1].ansB);
	}
}SegTree;
int n,q,p,v;
void solve(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&v);
		SegTree.dat[i]={v-i,v+i};
	}
	SegTree.build(1,1,n);
	printf("%lld\n",SegTree.query());
	for(int i=1;i<=q;i++){
		scanf("%lld%lld",&p,&v);
		SegTree.dat[p]={v-p,v+p};
		SegTree.update(1,p);
		printf("%lld\n",SegTree.query());
	}
}
signed main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	freopen("code.out","w",stdout);
#endif
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Happy New Year!\color{green}\text{Happy New Year!}