题解：P14306 【MX-J27-T3】旋律

· · 题解

闲聊：当时切这个题的时候把负号抄成正号了……QAQ

题目传送门

“更差的阅读体验”

1. 排序

首先，我们注意到原序列各个数之间的内部顺序并不重要，所以我们先将原数组排序，这样方便后续处理。

原数组排完序后，它就变成了几块的数字，每一块数字都落在一段区间内，且它们的值都是相等的。这样几个数字块会按值的大小从小到大排列。

比如样例的第 2 组数据，排完序后就是： 1 1 1 4 4 5 （没有那么臭了对不对）

这样做有个什么好处呢，值单调不降，越靠后的数一定越大，这样求区间最大最小值就不用再扫一遍序列了。

这样也很方便我们后续观察。

2. 最优选法 & n^3 做法

我们发现最优的选法一定是选了连续的一段数，也就是对于某个确定的区间 [l,r]，值落在 [l,r] 这个范围内的数都选上一定是更优的。

证明也很简单，假设你选了一些数字，最小值是 l，最大值是 r，那么它们的极差是确定的（也就是 r-l）。额外多选落在 [l,r] 这个范围内的数并不会改变极差，却能增加长度，所以一定更优。

至此我们说明了最优解一定是，全选 值在某个范围内的数 后 得到的子序列。然鹅这个数组的值域太大了，我们需要对其先进行离散化。

（记 len 为离散化后数的个数）

（下面所说的数均指离散化后的数，原数我们用一个数组 zhen 储存，其中 zhen_i=x 代表 i 离散化前是 x。）

如果我们暴力枚举 l,r，然后暴力求出该范围内有多少数，时间复杂度是 O(n^3) 的，无法接受。

3. n^2 做法

我们开一个桶数组，num_i 表示 i 这个数在序列里出现了多少次。这样对于一个值域区间 [l,r]，它的答案就是 k \times \sum\limits_{i=l}^{r} {num_i}-(zhen_r-zhen_l)。

前面是个 sigma 诶！可以用前缀和数组进行优化诶！所以我们再开一个 sum 数组求 num 数组的前缀和。答案就变为 k \times sum_r - k \times sum_{l-1}-(zhen_r-zhen_l)。

如果直接枚举 l,r，恭喜你拿到了 O(n^2) 解法。

4. 正解

最终答案是什么？是所有前面这样的区间 [l,r] 的答案取最大值对吧。如果我们只枚举一个 l，然后稍微将上面的式子变一变形，也就是 zhen_l - k \times sum_{l-1}+(k \times sum_r-zhen_r)。

所以对于一个 l，以它为左端点的所有区间里，最大的值就是 zhen_l - k \times sum_{l-1}+\max\limits_{r=l}^{len}{(k \times sum_r-zhen_r)}。

我们接下来要做的就是快捷地求出来 \max\limits_{r=l}^{len}{(k \times sum_r-zhen_r)}。

如果我们倒序枚举 l 呢？那 r 的取值区间每次只会多一个数字（即当前的 l）。

让 ma 表示 \max\limits_{r=l}^{len}{(k \times sum_r-zhen_r)}，这样每次枚举到一个 l，用 k \times sum_l-zhen_l 更新一下当前 ma 值，然后再利用 ma 里面的最大值求解左端点为 l 时的最大值（记作 f_l）即可。

最终答案为 \max\limits_{l=1}^{len}{f_l}。

代码：

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

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

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}

const int N=1e5+5;
const int inf=1e16;
int qwq,T,n,k,a[N],b[N],zhen[N],num[N],sum[N];
//数组名全部同题解 

inline void INIT(){
    for(int i=0;i<=n;i++){
        zhen[i]=num[i]=sum[i]=0;
    }
}

signed main(){
    qwq=read(),T=read();
    while(T--){
        n=read(),k=read();
        INIT();//多测记得初始化 
        for(int i=1;i<=n;i++){
            a[i]=read();
            b[i]=a[i];
        }

        //离散化 
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        int len=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;i++){
            int pos=lower_bound(b+1,b+len+1,a[i])-b;
            zhen[pos]=a[i];
            num[pos]++;
        }

        //前缀和处理 
        for(int i=1;i<=len;i++){
            sum[i]=sum[i-1]+num[i];
        }
        int ans=-inf,ma=-inf;
        //k*sum[l]-zhen[l]会出现负数，所以ans,ma初始化要给一个极小值  
        for(int l=len;l>=1;l--){
            //同题解的讲解 
            ma=max(ma,k*sum[l]-zhen[l]);
            ans=max(ans,ma+zhen[l]-k*sum[l-1]);
        }
        write(ans);printf("\n");
    }
    return 0;
}