UOJ246 【UER #7】套路题解

题意：

反攻正在进行中，按照套路，跳蚤国将会很快获得最终的胜利。跳蚤国的情报局也没闲下来，他们正打算派遣一批 “菲克蚤” 前往跳晚国窃取有关三星 note7 的资料。

cxy 是这批 “菲克蚤” 的教练，他教会他们各种 Fake 的技术，以便更好混入敌方内部。共 \(n\) 只菲克蚤，由 \(1\) 到 \(n\) 编号。cxy 给每个菲克蚤都算了特征值 \(a_1, \dots, a_n\)，两个菲克蚤的相似度定义成这两个菲克蚤的特征值的差的绝对值，即第 \(i\) 只菲克蚤与第 \(j\) 只菲克蚤的相似度为 \(\lvert a_i - a_j \rvert\)。

现在这批菲克蚤排成一列在 cxy 面前，cxy 需要在其中选出一些菲克蚤合成一个行动小队。按照套路，他会选取连续一整段的菲克蚤 \(a_l, a_{l + 1}, \dots, a_r\)。很显然，这个行动小队越大越好，但是按照套路，小队内的跳蚤最好都各不相同，假如有两只跳蚤长得很像的话很可能会引起跳晚们的怀疑。为此 cxy 将小队的相似度定义为小队中的跳蚤两两之间的最小的相似度，用 \(s(l, r)\) 表示。

为保证安全，现在他想选取至少 \(k\) 只跳蚤，且使得安全值最大。其中安全值定义如下：

\[ \begin{equation} s(l, r) \times (r - l) \end{equation} \]

但是，他并不知道最优解是什么，于是按照套路你需要帮助他求得这个值。

输入格式：

按照套路，第一行三个正整数 \(n,m,k\)。\(k\) 的意义如前所述，\(n\) 表示跳蚤的只数。

接下来一行 \(n\) 个整数，按照套路依次表示 \(n\) 只跳蚤的特征值 \(a_1, \dots, a_n\)，保证 \(1 \le a_i \le m\)。

输出格式：

按照套路，一行一个整数，表示答案。

数据范围：

在所有数据中，满足 \(2 \le n \le 2\times 10^5,~1 \le m \le 2\times 10^5,~2 \le k \le n\)。

这里区间长度的定义~~十分鬼畜~~，即定义 \([l,r]\) 的长度为 \(r-l\) 。

因此下文中提到的区间长度均为 \(r-l\)

这个安全值主要的复杂度就在 \(s(l,r)\) 的计算上。

考虑区间dp求出这个 \(s(l,r)\) 。不妨称 \(s(l,r)\) 为 \(\mathtt{mingap}\) （最小差值）。

设 \(f_{i,j}\) 表示 \([i,j]\) 的 \(\mathtt{mingap}\) ，则 \[ f_{0,i}=+\infty,~f_{i,n+1}=+\infty,~f_{i,i}=0 \\ f_{i,j} = \min\left\{|a_i - a_j|, ~ f_{i,j-1} ,~f_{i+1,j}\right\} \] 显然这是一个 \(O(n^2)\) 的dp，并且没有优化的方法。

但是根据直觉，你不觉得这个区间长度足够大的时候，\(\mathtt{mingap}\) 会在某个区间内吗？

事实上确实如此。对于长度大于 \(k\) 的区间（显然它至少有 \(k+2\) 个数）

由于题目说了每个数一定是 \([1,m]\) 的某个整数。

根据平均值的性质（平均值原理？）可知区间的 \(\mathtt{mingap}\) 一定不超过 \(\dfrac{m}{k+1}\) 。

证明：

首先平均值的性质指 \(n\) 个非负数的和为 \(m\) ，则最小值最多为 \(\frac{m}{n}\) ，这个很显然。

接下来的证明来自我们熟悉的 Roundgod 。（以下是QQ聊天的截图）

简单来说就是构造差分数组 \(c_{0,1,\cdots,k+2}\) ，然后 \(\sum_{i=1}^{k+1} c_i = b_{k+2}-b_1 \le m\)

则 \((\min\{c_i\})_{\max} \le \frac{m}{k+1}\) 。\(\square\)

因此我们可以按照分块的思想，设一个阈值 \(s\)

对于长度小于 \(s\) 的区间，我们使用暴力区间dp计算 \(\mathtt{mingap}\) ，这部分的时间复杂度 \(O(ns)\)

对于长度大于 \(s\) 的区间，根据刚刚的推导，它最大的 \(\mathtt{mingap}\) 不会超过 \(\frac{m}{l+1}~(l>s)\)

因此我们可以考虑枚举右端点和 \(\mathtt{mingap}\) 值，来找到满足条件的最小左端点，以最大化区间长度

具体地，设 \(r_i\) 表示值为 \(i\) 的数最后出现的位置。

然后我们枚举 \(a\) 和 \(\mathtt{mingap} = j\)

并对 \(a_i \pm j\) 寻找对应的位置，并记 \(g_j\) 表示 \(\mathtt{mingap}\) 为 \(j\) 时目前最左可能的位置，维护下就好了

这部分的时间复杂度为 \(O(n\times\frac{m}{s+1})\)

因此总复杂度 \(O\left(ns + n \times \dfrac{m}{s+1}\right)\) ，根据基本不等式显然取 \(s=O(\sqrt{m})\)

同时注意到 \(f_{i,j}\) 从 \(f_{i,j-1}\) 和 \(f_{i+1,j}\) 推导而来，考虑滚动数组。

故时间复杂度 \(O(n \sqrt{m})\) ，空间复杂度 \(O(n)\) ，可以通过此题。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,m,k,s,a[N],r[N],g[N],f[2][N],ans[N];
void init(int idx){for(int i=0; i<=n; i++) f[idx][i]=INF;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k; --k; s=sqrt(m);
    for(int i=1; i<=n; i++) cin >> a[i];
    int now=0,to=1; init(to);
    for(int i=1; i<=s; i++)
    {
        swap(now,to); init(to);
        for(int j=1; j<=n-i; j++)
        {
            f[to][j] = min({ abs(a[j]-a[j+i]), f[now][j], f[now][j+1] });
            up(ans[i], i * f[to][j]);
        }
    }
    for(int i=1; i<=n; r[a[i]] = i, i++)
        for(int j=0,l=0; j*(s+1) <= m; j++)
        {
            up(ans[i-l-1], (i-l-1) * j);
            up(g[j], r[max(0ll, a[i] - j)]);
            up(g[j], r[min(m+1, a[i] + j)]);
            up(l, g[j]);
        }
    cout << *max_element(ans + k, ans + n + 1) << '\n';
    return 0;
}

后记（来自题目）

凭借着情报局的资料，跳蚤国很快研制出了高仿三星 note7，并加以改进，去掉了外面的手机外壳，暴露了其炸弹的本质，还在前端绑上了一个 Nokia1050，威力大增。

按照套路，失去了唯一优势的跳晚国很快败下阵来，跳蚤国获得最终的胜利！

然而谁都不曾思考过，为什么跳蚤大陆会出现这种新型科技——手机……

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/uoj246.html

q779

https://q779.cn/2022/09/12/uoj246-uer-7-tao-lu-ti-jie/