CF1706D2 Chopping Carrots (Hard Version) 题解

题目链接：CF1706D2 Chopping Carrots (Hard Version)

题意：

这是该问题的困难版本。两个版本间的区别仅为 $n$、$k$、$a_i$ 和 $\sum n$ 的上界。

注意不正常的空间限制。

给出长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$，以及一个整数 $k$。

一个长度为 $n$ 的整数数组 $p_1, p_2, \ldots, p_n$ 的花费为 $\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right)$。

此处，$\lfloor \frac{x}{y} \rfloor$ 表示 $x$ 除以 $y$ 的整数部分。

请找到花费最小的数组 $p$，且满足对任意 $1 \le i \le n$ 都有 $1 \le p_i \le k$。

输入格式：

第一行包括一个整数 $t$（$1 \le t \le 100$），表示接下来测试组的数量。

对于每一个测试组，第一行包括两个整数 $n$ 和 $k$（$1 \le n, k \le 10^5$）。

对于每一个测试组，第二行包括 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^5$）。

保证 $\sum n \le 10^5$。

输出格式：

对于每一个测试组，输出一个整数，表示满足上述条件的数组 $p$ 的花费的最小值。

想到了枚举一个维护一个，但是因为没看简单版思路错了。不过这道题还是很有趣的。

简单版数据范围是 $n,k\le 3000$ ，我们可以预处理出所有当 $p\in[1,k]$ 时 $\left\lfloor\dfrac{a_i}{p}\right\rfloor$ 的取值。

然后枚举最小值，并二分出对于每个 $i$ 的最小的大于当前最小值的 $\left\lfloor\dfrac{a_i}{p}\right\rfloor$ 的值，记为 $w_i$ ，取 $w_i$ 的最大值。

困难版（本题）其实不难。显然预处理用数论分块优化一下，接着我们来考虑怎么优化这个二分。

直接存所有的 $\left\lfloor\dfrac{a_i}{p}\right\rfloor$ 空间可能会炸，因此我们可以维护一个数组 $\mathtt{mx[i]}$ 表示 $i$ 作为最小值时的那个 $w_i$ 。

在计算出每个 $i$ 的 $\left\lfloor\dfrac{a_i}{p}\right\rfloor$ 的所有取值后，我们依次尝试更新 $\mathtt{mx[tmp[j]]}$ 其中 $\mathtt{tmp[j]}$ 表示第 $j$ 个可能取值。

统计答案的话需要维护一个 $\mathtt{mx2}$ ，用于更新 $w_i$ 的最小值，初始时是每个 $i$ 的最小 $\left\lfloor\dfrac{a_i}{p}\right\rfloor$ 取值 $\min\{\mathtt{tmp[1]}\}$

在枚举最小值的过程中，我们用 $\mathtt{mx2}-i$ 更新答案，然后 $\mathtt{mx2}\operatorname{\uparrow}\mathtt{mx1[i]}$ ，这样就可以得到最终答案了。

不得不说，这个 $\mathtt{mx[]}$ 数组是真的很妙，把慢悠悠的二分换成了直接 $\mathcal{O}(1)$ 查询，很有意思。

时间复杂度 $\mathcal{O}(n\sqrt{M})$ ，其中 $M$ 为 $a_i$ 的值域上限

代码：

#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)(1e5 + 15))

int a[N],tmp[N],mx[N];
void solve()
{
    memset(mx, 0, sizeof(mx));
    int n,k,mx2 = 0; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for(int l = 1, r = 0; l <= min(k, a[i]); l = r + 1) {
            r = a[i] / (a[i] / l); tmp[++cnt] = a[i] / l;
        }
        if(k > a[i]) tmp[++cnt] = 0;
        reverse(tmp + 1, tmp + 1 + cnt); up(mx2, tmp[1]); tmp[cnt + 1] = INF;
        for(int j = 1; j <= cnt; j++) up(mx[tmp[j]], tmp[j + 1]);
    }
    int res = INF;
    for(int i = 0; i <= 1e5; i++) { down(res, mx2 - i), up(mx2, mx[i]); }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}