自动搬运

查看原文

来自洛谷，原作者为

	rnfmabj 希望别人想到我不是在想我的退役

搬运于2025-08-24 22:44:57，当前版本为作者最后更新于2024-07-17 18:00:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

题目传送门

给定长为 $n$ 的排列 $a$。

定义区间 $[l, r]$ 的权值如下：将区间内的数从小到大排序，设 $x$ 为区间长度（即 $r - l + 1$）$y$ 为区间中位数，则该区间的权值为 $x + 2y$。

求所有 $\frac{n(n + 1)}{2}$ 个区间中权值的最大值和最大值的个数。

理清思路

首先很显然的一件事是最大值一定是 $2 \times n +1$，因为它取全部的数字之后的值就是 $2 \times n +1$。

然后我们仔细想想，若是想要最大值是 $2 \times n+1$，我们取的中位数 $k$ 一定要大于 $\frac{n}{2}$。

既然知道了最大值以及中位数 $k$ 的值，我们就可以找出序列的长度，手搓几个样例之后，我们发现这其中有一半的值是大于我们所找到的中位数 $k$ 的，而在整个序列中大于这个中位数 $k$ 的值恰好就只有该序列长度的一半个。

知道了这一点后，我们就可以预处理出大于该中位数 $k$ 的最左边的和最右边的值，并将它们的下标用 $l,r$ 表示，如果 $r-l+1>$ 该序列的长度，则没有答案，否则就有 序列长度 $-(r-l+1)+1$ 个答案，最后，我们在判断一下越界情况，就 $A$ 了一道绿题了！

代码

有了综上所述的思路之后，第一个问题时候怎样找左值 $l$ 和右值 $r$，用递推的思路，去找上一个中位数的左值 $l$ 和右值 $r$，取 $l$ 与自身坐标的最小值作为自己的 $l$，右值 $r$ 则取最大值。

第二个问题是如何判越界，如果我们当前要补 $s$ 个数才可以达到需要的长度，当 $l≤s$ 是说明是左边越界，要将答案减去 $s-l+1$ 个（至于为什么，读者可以自行想想）。当 $r+s>n$ 时说明是右边越界，此时，答案就要减去 $r+s-n$ 个。

AC code

#include <bits/stdc++.h>
using namespace std;
long long n,ans,ansl,a,bot[3000010],l=INT_MAX,r=1,k,L,s;
//ans为所求最大值，bot用于存每个数字的位置，l和r代表最左值和最右值，L是区间长度，k是所需长度，s代表要补几位
int main(){
	scanf("%lld",&n);
	ans=2*n+1;//z计算最大值
	for (int i=1;i<=n;i++){
		scanf("%lld",&a);
		a*=2;//我直接乘二存的，便于后面求值
		bot[a]=i;//记录下标
	}
	for (int i=n*2;i>n;i--){//枚举所有可行的中位数
		if (bot[i]==0)bot[i]=bot[i-1];//如果没有被标记过，说明是中位数是，让他的下标等于比他大的值，再去求 l 和 r
		r=max(bot[i],r);
		l=min(bot[i],l);//寻找左值和右值
		k=ans-i,L=r-l+1,s=k-L;//计算
		if (L<=k){
			ansl+=s+1;//统计答案
			if (l<=s)ansl-=(s-l+1);
			if (r+s>n)ansl-=(r+s-n);//判断越界
		}
	}
	printf("%lld %lld",ans,ansl);//输出
	return 0;//完结撒花
}