牛客挑战赛36 E&F

E

考虑一个人 \((a_i,b_i)\) 满足什么条件会自闭。设比其能力值低的人的数量为 \(p\)，现在已经有 \(l\) 个能力值比其低的人退出，\(r\) 个能力值不比其低的人退出，那么 TA 在下一场考试中不自闭需要满足不等式 \((p-l)a_i \geq n-r-l-1\)，即 \(l(a_i-1)-r \leq pa_i-n+1\)。

对于一个人的离开对于其他人的 \(l,r\) 会产生一定影响，对 \(r\) 产生的影响好办，但是对 \(l\) 产生的影响不易处理。单独把不等式中的 \(l\) 拿出来考虑，令 \(a_i \neq 1\)，不等式等价于 \(l \leq \frac{pa_i+r-n+1}{a_i-1}\)。

设 \(mx_i = \frac{pa_i+r-n+1}{a_i-1}\)，\(mx_i\) 会随着 \(r\) 的增加变大。可以考虑维护每一个人的 \(mx_i\) 和 \(l_i\)，\(l_i\) 就变得易于维护，但是 \(mx_i\) 好像不太好办。

注意到 \(r\) 的最大增量为 \(n\)，而每种 \(a_i\) 至多出现两次，所以 \(mx_i\) 在整个过程中的增量之和是不会超过 \(2(\sum\limits_{j=1}^\frac{n}{2} \frac{n}{j}) = O(n \log n)\) 级别的。这样如果我们能够以较快的复杂度定位到进行一次修改之后将要变大的 \(mx_i\) 并将其修改，那么修改次数就是 \(O(n \log n)\) 的。

使用线段树，每一个节点维护以下两个信息：

• 该节点对应区间中 \(mx_i - l_i\) 的最小值；
• 对该节点对应区间的所有 \(r_i\) 进行区间 \(+1\)，至少进行多少次使得存在一个 \(mx_i\) 相比当前记录的值变大。

一次退出可以对应这两个信息的区间修改。找到需要修改的 \(mx_i\) 可以利用第二个信息在线段树上进行寻找，如果当前第二个信息的值 \(>0\) 则无需修改，否则进入左右儿子进行修改。而找到需要退出的人则可以利用第一个信息进行类似的寻找。需要在预处理时特殊处理 \(a_i = 1\) 的情况。

复杂度 \(O(n \log^2 n)\)。

F

首先任意一个购买方案都可以用一个购买序列描述，我们按照该序列依次购买土地，不考虑并没有购买完该序列中的所有土地之前达成条件的情况（此时购买序列应该是当前序列的前缀），购买完这些土地之后坐等满足条件。下文中的所有购买序列都是表示这样的意思。

对最优的购买方案进行分析，可以得到以下结论：

• 对于一个购买序列，最优的购买方案一定是能买就买，即依次考虑该序列中的土地，如果当前能够买下则立即买下，否则不断攒钱直到恰好可以买下该土地时立即购买。

Proof. 因为购买花费的总代价确定，所以每天的收益越多越好，而在这样的贪心策略下能够让每一天的收益均最大化，故为最优策略。

接下来的讨论均建立在该最优策略之上。

• 对于一个购买序列 \(p_1,p_2,\ldots,p_k\)，设在最优策略下在第 \(q_i\) 天购买 \(p_i(i \in [1,k])\) 号土地，在买下该土地之后剩余钱数为 \(w_i\)。如果 \(q_i \neq 0\)，则 \(w_i < \sum\limits_{j=1}^{i-1}b_i\)。

Proof. 若 \(w_i \geq \sum\limits_{j=1}^{i-1}b_i\) 则可以在第 \(q_i - 1\) 天就买下该土地，不符合最优策略。

• 对于两个购买序列 \(p_1,p_2,\ldots,p_m\) 和 \(q_1,q_2,\ldots,q_n\)，其中 \(\sum\limits_{i=1}^m b_{p_i} = \sum\limits_{j=1}^n b_{q_j}\)。在最优策略下，设按照两个序列购买下 \(p_m\) 和 \(q_n\) 的天数分别为 \(T_p\) 和 \(T_q\)。如果 \(T_p \neq T_q\) 则天数较小的购买序列答案一定更小，反之则剩余钱数较多的答案一定更小。

Proof. \(T_p = T_q\) 的情况是显然的，对于 \(T_p \neq T_q\) 的情况不失一般性地假设 \(T_p < T_q\)。那么在 \(T_q\) 天 \(p\) 方案手上拥有的钱数 \(\geq \sum\limits_{i=1}^m b_{p_i}\)，而根据上面的结论 \(q\) 方案手上拥有的钱数 \(< \sum\limits_{i=1}^m b_{p_i}\)，故 \(p\) 方案更优。

也就是说我们现在可以量化在购买土地的总收益相等的情况下哪一个序列是最优的方案了，也就是以购买完所有土地的时间为第一关键字、买完所有土地时剩余的钱为第二关键字的最小方案。接下来我们需要知道如何找到这样的方案。

• 对于一个购买序列 \(p_1,\ldots,p_k\)，如果这个序列是在与其总收益相等的所有序列中最优的序列，则其任意前缀也会是在与这个前缀总收益相等的所有序列中最优的序列。

Proof. 如果不满足，则换成对应前缀的最优序列更优。

这样可以发现最优的购买序列满足子问题性质。考虑 DP：设 \(f_i\) 表示总收益为 \(i\) 的所有序列中最优序列的买下所有土地的时间和买下所有土地时剩余的钱。转移枚举下一个土地买谁即可。复杂度 \(O(n \max c_i)\)。

找到了 \(f_i\) 后考虑一组询问 \((c_i,d_i)\) 如何解决。枚举最后一次购买后土地总收益 \(p\)，那么最优的方案一定是 \(f_p\) 对应的方案。而如果选择了 \(f_p\) 对应的方案作为最优方案，则忽略在购买完所有土地之前的部分，其收益与时间的图像构成一条直线。我们需要求出 \(f_1 \sim f_{c_i}\) 这些直线最小在横坐标为多少的时候纵坐标大于等于 \(d_i\)，对于所有 \(d_i\) 能够作为最小横坐标的直线显然构成一个下凸壳，将询问离线并按照 \(c_i\) 从小到大排序，然后依次加入直线维护下凸壳，每一次询问在凸壳上二分找到最优点即可。

最后一个问题是在实际操作过程中需要将 \(f_p\) 看做完整的一条直线，如果最优的直线恰好是 \(f_p\) 对应直线且对应横坐标小于购买完 \(f_p\) 最后一块土地的时间，算法就 GG 了。但是由于 \(f_p\) 对应序列的任意前缀都一定已经加入，且这些直线在横坐标小于购买完 \(f_p\) 最后一块土地的时间的任意一个横坐标的最大值一定大于 \(f_p\) 直线的对应位置的值，所以并不会存在这样的情况。

总复杂度 \(O(n \max c_i + (q + \max c_i) \log \max c_i)\)。