0x00 题目翻译
一个长度为 $n$ 的序列，求出对于所有 $1\le l\le r\le n$，
$$
\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r - l)
$$
的最大值。
每一组数据，先输出这个序列的答案，之后 $q$ 行修改操作，每行的 p x 表示把 $a_p$ 修改为 $x$，修改对之后的所有操作有影响，每一次修改后，输出新序列的答案。
0x01 解题思路
解题的关键就是对这个式子进行变形：
$$
\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r - l)
$$
首先观察到，选取的最大最小值一定在区间的两端（如果不在两端，那么可以去掉左右无用的部分，答案一定更优），于是式子变为：
$$
\vert a_l-a_r\vert- (r - l)
$$
绝对值意味着分类讨论，因为这里要求的是最大值，所以可以简单地去掉绝对值后对两种情况取最值：
$$
\max{a_l-a_r- (r - l),a_r-a_l- (r - l)}
$$
发现 $(r-1)$ 是一个和序列无关的整体，这并不好处理，可以想到合并到序列（我是看了题解才想到的）：
$$
\max{(a_l+l)-(a_r+r),(a_r-r)-(a_l-l)}
$$
这样就可以使 $(l-r)$ 和序列成为一个整体，为了方便表示和处理，令 $x_i=a_i+i$，$y_i=a_i-i$，于是变为：
$$
\max{x_l-x_r,y_r-y_l}
$$
这个时候就可以开始求答案了。
看到区间和修改，想到了线段树和区间DP，可以尝试结合这两者解决问题。
首先，对于题目的修改，想到用线段树去维护 $x$ 和 $y$ 两个序列，然后想怎样在线段树的合并（建树）中完成答案的求解。
线段树在建立的过程中不断合并左右两个子区间，求解也是类似的，每一次维护 $ans_1=x_l-x_r$，$ans_2=y_r-y_l$，结果就是 $\max{ans_1,ans_2}$，但还没有这么简单，接下来对区间进行讨论：
- 答案出现在左区间，直接取出计算完的数值；
- 答案出现在右区间，直接取出计算完的数值；
- 答案取自左区间和右区间，计算新的答案。
得出方程（符号表示有点混乱，具体看代码）：
$$
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;
};
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;
}
|
$$
\color{green}\text{Happy New Year!}
$$
