题解：P9053 [PA2021] Ranking sklepów internetowych

· · 题解

题目大意

题目传送门

给定长为 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;//完结撒花
}