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/