P9755 解题报告

· · 题解

前言

什么一眼题。

为什么我第一眼还能不会 2\log，速来嘲笑。

思路分析

首先注意到函数里有个对 1 取 \max，先给这个处理掉。

看一眼数据范围发现 b_i\ge 1，所以只有当 c_i<0 的时候这个才会有贡献。

对于 c_i<0 的先把这个断点先处理出来，然后接着考虑怎么做这个东西。

这个天数显然是非常有影响的，因为如果天数多了对 c_i 的影响也就多了，直接算出天数看起来就很不可取。

考虑二分出天数 x，接着我们就可以对每个地块上的数计算出 d_i，满足至少要第 d_i 天在这个地块种树才可以满足条件。

处理出这个之后我们就可以进行 check。

考虑一个非常暴力的做法，按照 d_i 从小到大处理，每次种下地块 i 的树，此时的代价就是 1\rightarrow i 还没种树的区块数，然后 1\rightarrow i 的区块都种下树。

直接树剖+线段树维护可以做到 \log^2，配合上外层可以做到 O(n\log^2 n\log V)。

但其实直接按这个天数排序对于点暴力往上跳打标记也是对的，可以做到单 \log。

接着回到上面那个问题怎么处理出 d_i。

首先我们有了树每天生长的一个高度的函数图，然后可以进行分讨。

  1. 对于 c_i=0 的情况，那个函数就是一条直线，直接算出 d_i 即可。
  2. 对于 c_i>0 的情况，那个函数是一条上升的直线，考虑计算 d_i 到 x 的函数和 x 轴围成的面积，不难发现这就是一个梯形，可以二分也可以直接算。
  3. 对于 c_i<0 的情况，函数就是一条下降的直线最后再拼上一条 y=1 的直线，计算上考虑先把图形分割了，前面还是梯形，后面还是一个矩形，可以先把矩形直接剥掉然后套用 2 计算。

然后讲下具体的实现问题。

目前的所有题解好像都用到了 __int128 和两次二分，实际上上面那个部分的实现可以做到不用二分，而且也不用 int128。

笔者比较菜所以只是没用 int128，但是优化还是非常显著的，三只 \log 的树剖直接草过去了。

具体的，我们发现实在计算时梯形面积是 10^{18} 级别的，但是 a_i 只有 10^{18} 级别。

也就是我们可以考虑，直接计算 \frac{10^{18}}{|c_i|}，拿这个值和梯形面积对比一下，要是梯形面积更大，就直接给 c_i 的贡献记作 a_i+1，否则就正常算出 c_i 贡献。

注意不能直接用 \frac{a^i}{|c_i|} 与梯形面积对比的方法比是否可行，因为有精度误差。

但是我们可以粗略的估计出会不会爆 10^{18}，所以用上面那个方法就可以了。

此时的误差最多只有 |c_i|-1，只有 10^9 级别，随便算不用担心爆。

代码

给两份，第一个树剖实现，O(n(\log^2 n+\log V)\log V)。

link。

第二个正常实现，O(n\log n\log V)。

link.