闲聊：当时切这个题的时候把负号抄成正号了……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\) 做法
先优化到 \(O(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\) 值，然后再求解左端点为 \(l\) 时的最大值（记作 \(f_l\) ）即可。
最终答案为 \(\max\limits_{l=1}^{len}{f_l}\)。
代码：
P14306
#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;
}