本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-05 17:43:13

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

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$ 的最大值。
数据范围：

• $1\le n,q\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^9$
• $1\le k\le 10^9$

显然，一个数被操作奇数次才可能被加。

注释 $1$：对于 $\{x_{2k}\}$,$\forall i\in[1,2k),x_i<x_{i+1}$，则 $\forall i\in[1,k],x_{2k-1}-x_{2k}<0$，其和显然小于 $0$。

所以说，为了让 $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$ 即可。

代码