[CF1098E] Fedya the Potter 题解

前言

一道类欧好题。

题解

这道题让求 \(c\) 数组的中位数，那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 \(\mathcal{O}(n^2)\) 项，考虑如何优化。

因为 \(b\) 数组的每一项都是 \(a\) 数组的一个区间 \(\gcd\)，这里就有一个比较常用的结论就是 \(b\) 数组中只有 \(\mathcal{O}(n\log w)\) 个本质不同的项（\(w\) 为 \(a_i\) 的值域），因为 \(a_i\) 的所有质因子次幂之和为 \(\mathcal{O}(\log{a_i})\)，而求 \(\gcd\) 的过程本质上是给质因子降幂的过程，所以如果在 \(a\) 数组中固定一个 \(l\) 端点，那么当 \(r\) 端点不断向右移动的过程中 \([l,r]\) 的 \(\gcd\) 最多只会变化 \(\log w\) 次，故 \(b\) 数组中总共只有 \(\mathcal{O(n\log w)}\) 个本质不同的项。

有了上述结论，我们可以考虑将 \(b\) 数组中每个元素写成二元组 \((val_i,num_i)\) 的形式，表示值为 \(val\) 的元素个数总共有 \(num\) 个。那么，如何通过遍历这个二元组来算出来区间数呢？

首先考虑如果是正常的 \(b\) 数组（即每一项 \(num\) 都是 \(1\)）怎么做：可以双指针维护。移动 \(r\) 指针，然后将 \(l\) 指针移动到最靠左的满足区间和小于 \(mid\) 的位置计算即可。所以对于这个二元组，我们依旧尝试使用双指针维护答案。

首先我们将 \(b\) 数组按照 \(val\) 从小到大排序，然后我们从左到右移动 \(r\) 指针，然后修改 \(l\) 指针，其中 \(l,r\) 指针不一定在整数位置，而是有可能将某一项分成了两部分。为了表述方便，下文表示方式如下：

\(l,r\) 分别表示 \(l\) 指针和 \(r\) 指针所在的位置在 \(b\) 数组中的下标。
\(num_i,val_i\) 分别表示 \(b\) 数组第 \(i\) 项元素的两个信息。
\(mem_l\) 表示 \(b_l\) 这一项中有 \(mem_l\) 项值为 \(val_l\) 的元素在 \(l\) 指针右侧（包括 \(l\) 指针）。
\(tmp_r\) 表示 \(b_r\) 这一项中有 \(tmp_r\) 项值为 \(val_r\) 的元素在 \(r\) 指针左侧（包括 \(r\) 指针）。
\(hve_r\) 表示 \(b_r\) 这一项中有 \(hve_r\) 项值为 \(val_r\) 的元素在 \(r\) 指针右侧（不包括 \(r\) 指针，即 \(tmp_r+hve_r=num_r\)）。
\(sum_i\) 为 \(num_i\) 的前缀和。
\(cost_i\) 为 \(val_i\times num_i\) 的前缀和。
\(mid\) 表示当前二分答案的值，我们要求的是有多少个区间的区间和不超过 \(mid\)。
\(now\) 当前区间的区间和。
为表述更形象下文将 \(b\) 数组中的二元组称为一个区块。

因为我们每一次对于每一个 \(r\) 指针都是要找到一个最靠左的合法 \(l\) 指针，而在 \(b\) 数组的同一项内区间和为等差数列，所以说在同一项内当我们的 \(tmp_r\) 增加了 \(x\) 时， \(mem_l\) 的值将变化到 \(\lfloor\dfrac{mid - cost_{r-1}+cost_{l}-(tmp_r+x)val_r}{val_l}\rfloor\)。这个式子是一定正确的，不会算多，具体说明我们放在最后。那么我们要计算此时的合法区间数的时候就是计算最大合法区间长度，也就是：

\[\lfloor\dfrac{mid - cost_{r-1}+cost_{l}-(tmp_r+x)val_r}{val_l}\rfloor+sum_{r-1}-sum_l+tmp_r+x \]

那么由于有很多合法的 \(x\) 都能保证变化结束之后 \(l,r\) 指针都仍然能在变化之前的区间，所以就是对于所有合法的 \(x\) 将上面的式子求和，也即：

我们记 \(mx\) 为最大的合法的 \(x\)，容易发现 \(mx=\min(hve_r,\lfloor\dfrac{mid-now+mem_l\times val_l}{val_r}\rfloor)\)。则答案为：

\[\begin{aligned} &\sum_{x=1}^{mx}\lfloor\dfrac{mid - cost_{r-1}+cost_{l}-(tmp_r+x)val_r}{val_l}\rfloor+sum_{r-1}-sum_l+tmp_r+x\\ =&\sum_{x=0}^{mx-1}\dfrac{val_r\times x+mid-cost_{r-1}+cost_l-tmp_r\times val_r-mx\times val_r}{val_l}+mx\times (sum_{r-1}-sum_l+tmp_r)+\dfrac{mx(mx+1)}{2} \end{aligned} \]

如果记 \(f(n,a,b,c)=\sum_{i=0}^{n}\lfloor\dfrac{a\times i+b}{c}\rfloor\)，那么就是：

\[f(mx-1,val_r,mid-cost_{r-1}+cost_l-tmp_r\times val_r-mx\times val_r,val_l)+mx\times (sum_{r-1}-sum_l+tmp_r)+\dfrac{mx(mx+1)}{2} \]

\(f\) 函数是经典类欧，所以可以在 \(\mathcal{O}(\log w)\) 的复杂度内移动一次。而每一次计算都会导致 \(l\) 指针或 \(r\) 指针所属区块变化，故最多计算 \(\mathcal{O}(n\log w)\) 次，加上二分答案的复杂度，总复杂度为 \(\mathcal{O}(n\log^3 w)\)。当然这个复杂度在 \(\log\) 部分不够精确，但大致是这样的，可以通过本题。

当然上述做法正确的前提是在任何时刻 \([l,r]\) 区间和都恰好不超过 \(mid\)，所以在最开始的时候要特殊处理一下，不移动 \(l\) 指针，让 \(l\) 指针一直在最左边，然后不断移动 \(r\) 至不能移动位置，接下来才能按照上面的方法计算。同时如果 \(l\) 指针和 \(r\) 指针如果在 \(b\) 数组中的同一项的时候也需要特殊处理一下，具体的看代码。

好，现在来说明一下为什么上面的式子不会算多。首先如果 \(r\) 指针变化之后 \(l\) 指针所在的区块没有发生变化那么显然式子成立。否则：因为我们将 \(b\) 数组从小到大排序了，所以说每一次只要 \(r\) 指针变化之后， \(l\) 指针如果跳动到了下一个区间则按照上述 \(mem_l\) 一定不会超过 \(num_l\)，证明如下：

假设 \(l\) 指针跳动到了下一个区间后 \(mem_l>num_l\)，则设变化前区间和为 \(lst\)，变化前所在区间为 \(i\) 号区块，变化后区间为 \(j\) 号区块，变化前 \(tmp_l=p\)，变化后 \(tmp_l=q-num_j\)，变化过程中 \(r\) 指针移动带来的区间和变化为 \(W\)。那么就有：

\(q\ge 1\)

\(lst-p\times val_i+q\times val_j+W\le mid\)

\(lst-(p-1)\times val_i+W>mid\)

综上可推导出 \(val_i>val_j\)，与从小到大排序相矛盾，故命题成立。