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;
}