Red-Blue Operations (Hard Version) 题解

· · 题解

现在才发现已经一个半月没写题解了。

Red-Blue Operations (Hard Version)

题目考察：二分，前缀和（极值），贪心，排序。
题目简述：
给你一个序列 \{a_n\}，还有一个初始值均为 0 的序列 \{b_n\}，有 q 次询问，每次询问若有 k 次操作，对于第 i 次操作（i\in[1,k]），选择一个 j\in[1,n]，使得 a_j 加上 (1-num_j\bmod 2)\times i 后再将 num_j 加 1，最后求 \displaystyle\min_{i=1}^na_i 的最大值。
数据范围：

所以说，为了让 x_{2k-1}-x_{2k} 更大，我们让 x_{2k-1}-x_{2k}=-1，即对一个数的操作一定是一个区间。

考虑二分答案，二分数组最小值 x。在二分前将序列升序排序，以便我们快速找到小于数组最小值的数，这件事我们可以用二分实现。
二分找到小于该数的的数目 sum 后，贪心的想，我们肯定要把最后一次操作作用在第一个数上，如果这样，我们只能对他做 1 次操作。

注释 2：如果我们对其做 3 次操作，那么贡献为 k-(k-1)+(k-2)=k-1<k。

那么这样的话，\forall i\in[1,sum],a_i 将会变为 a_i+(k-i+1)，如果 \displaystyle\min_{i=1}^{sum}a_i+k-i+1<x，则无法达到目标。

注释 3：对于 a_i+k-i+1 我们可以将 k 提出，在一开始（排序后！排序后！排序后！）对 a_i-i+1 做前缀最小值，在 check 函数内再将 k 加回。

这时还剩 k-sum 次操作，在前面的 sum 个数上应该会有一些数比 x 要大，那么在那些数上进行 2 次操作，使该数减 1。

注释 4：若所有的数都比要求的数要小（sum=n）且剩余操作数为奇数，则需要撤销一个数的操作凑成偶数，但实际无法撤销任何一个数，故无法达到要求。

注释 5：若 num_i=\sum_{j=1}^ia_i+k-i+1，则在这些数上的操作数为 2(num_{sum}-sum\times x)，维护 num_i 的方法类比注释 3。

设还剩 lft=k-sum-2(num_{sum}-sum\times x) 次操作，那么剩下的就要在 i\in[sum+1,n] 的 a_i 上操作了。

注释 6：lft\le 0，直接判定可达到要求即可。

注释 7：若剩余一些操作（lft>0）且无剩余数（sum=n），则判定无法达到要求。

若 lft\bmod 2=1，则在一个数上操作一定会增加，证明请类比注释 1。
否则因为奇数加奇数为偶数，那么如果剩余两个数（n-sum\ge 2）则在两个数上分别操作奇数次，证明仍然类比注释 1。
否则只剩 1 个数，判定 \displaystyle a_n-\frac{lft}{2} 是否大于等于 x 即可。

代码