自动搬运

查看原文

来自洛谷，原作者为

	retep 离谱！世界太离谱了！（关注必互关）

搬运于2025-08-24 22:39:08，当前版本为作者最后更新于2022-07-25 01:00:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目简述

你有一个长度为 $n$ 的序列 $a$，它的一个区间 $[l,r]$ 的价值为：

$\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1$。

求这个序列价值最大的子区间并输出这个价值。

数据范围：$1\le n\le 4\times10^6$，$1 \leq a_i \leq 10^9$

题目传送门：P8446 虹色的北斗七星

题目分析

这是道最优化问题，关键点在于对问题的转化。

题目中最显而易见的一点是 $\max$ 与 $\min$ 的位置一定是该区间的两个端点。

说实话这题本蒟蒻在比赛时想了很久，从动态规划到二分答案甚至连分治都考虑过，不过全部以不可行告终 要不是普及组不能超纲，我肯定浪费更多时间。

我发现自己在之前的思考中都潜意识地将 $r-l+1$ 视作一个整体，也就是区间的长度，毕竟题目中也是用长度的意义来叙述的。

意识到这点后我开始想，是不是可以将 $r-l+1$ 分开呢？$1$ 很好说，只是个常量。关键在于 $r-l$，它俩其中一个是 $\max$ 的下标，另一个则是 $\min$ 的下标。

如果可以将 $r$ 与 $l$ 和 $\max$ 与 $\min$ 融合在一起就好了，因为那样的话就不用再受区间长度所困扰，只要求最大值和最小值就行了。可惜的是我们并不知道 $\max$ 和 $\min$ 哪个对应 $r$ 哪个对应 $l$ ......

于是乎，分类讨论！

1. 当 $\max$ 对应的下标是 $r$，也就是 $\max$ 在 $\min$ 右边时：$(\max-r)-(\min-l)-1$

2. 当 $\max$ 对应的下标是 $l$，也就是 $\max$ 在 $\min$ 左边时：$(\max+l)-(\min+r)-1$

解释一下，如果是第一种情况的话，我们建立 $b$ 数组，使 $b_i=a_i-i$，然后计算区间价值时，直接计算:

可以看出这时算出来的值正好是区间的价值。第二种情况的话使 $b_i=a_i+i$ 然后同理。

到这儿，我们已经可以将原问题转换为两个子问题了：

1. $b_i=a_i-i$，求 $b_i-b_j-1$ 的最大值，保证 $i>j$。

2. $b_i=a_i+i$，求 $b_j-b_i-1$ 的最大值，保证 $i>j$。

最后将两个子问题合并，既取其中的最大值，就得到了问题的最终答案。

code

#include<bits/stdc++.h>
#define N 4000005
#define ll long long
using namespace std;

int n,a[N],b[N],ans=-1;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=a[i]-i;
	for(int i=1,mn=1e9;i<=n;i++){
		mn=min(b[i],mn);
		ans=max(ans,b[i]-mn);
		b[i]=a[i]+i;
	}
	for(int i=1,mx=-1e9;i<=n;i++){
		mx=max(b[i],mx);
		ans=max(ans,mx-b[i]);
	}
	cout<<ans-1;
	return 0;
}