题解
整体思路
- 对b排序，同时保留b的原始下标。
- 计算每个$b_i$所对应的可用数字的数目，也计算其前面有多少个空缺。根据这两个值我们就可以计算出一个“额外可用数字的数目”。
- 我们找出最小的“额外可用数字数目”为0的$b_i$。
- 找出0到i的所有$b_j$中原始下标最小的j。并将当前最小的可用的值分配给$b_j$。
- 根据4的分配，重复#2及后面的步骤，直到所有数都被分配。
思路解析
我们先从#3入手。
我们考察每个$b_i$所对应的所能使用的数字个数。
比如对于$b=[3, 4, 7, 8]$中的3和4能使用的只有2个数：1和2，而对于7能使用的数和8一样都有4个：1、2、5、6。
也不难发现3和4可以用的两个数必须被分配给3和4，而不能分配给7和8。这是因为3和4有两个空缺，而3和4恰好只有2个数可以用。
进一步的，我们发现，3和4分配之后，7和8只剩下2个可以用的数，但是7和8的空缺也只剩下2个。（最初7和8可以用的数有4个，而空缺也有4个）。
因此我们可以得出一个结论：小的数的分配会影响大的数，我们应当优先处理较小的“额外数字的数目”为0的$b_i$。
比如$[3, 4, 7, 8]$，虽然4和8的“额外数字的数目”都是0，但是在#3，我们优先处理4，而非8。
接着我们回到#2。
我们计算空缺是只需要考虑比自己小的$b_i$有多少没有分配即可。因此3其实只有1个空缺，4有2个，7有3个，8有4个。
也就是说，3不考虑4的情况，7不考虑8的情况。
因为如果我们把b改成$[3, 5, 7, 8]$的话，3和5就不会需要提前处理。所以计算空缺时我们只需要计算有多少个$b_i$小于等于当前的值即可。
接着我们来看#4。
我们已经知道了1和2要分配给3和4。接下来的问题就是1具体要分配到哪。显然这就要靠#1保留的原始下标了。
我们将1分配给原始下标最小的即可。也就是如果原本4在3前面，则分配给4。
这里需要注意的是，我们分配完了1之后，并不能立刻分配剩下数（这个例子里只有2）。因为一次分配之后，剩下的数的“额外数字的数目”可能发生改变。
比如1分配给了4之后，3的“额外数目”由1变成0，因为原本3有2个数可以用但只有1个空缺，1分配给4之后，3只剩下2可以用。
这一点在样例6：$b=[8, 7, 4, 5]$（排序后$[4, 5, 7, 8]$）上更加明显。一开始只有8的“额外数目”为0，然后恰好8就是原始下标最小的数。但1分配给8之后，不能接着把2分配给剩余的原始下标最小的数（也就是7），而是要重新回到#2，提前处理4和5。
完整例子
我们以样例6为例：$b=[8, 7, 4, 5]$。
#1，我们排序并保留原始下标。我们得到$[(4: 2), (5: 3), (7: 1), (8: 0)]$。
#2，我们计算当前的“额外数目”。我们得到$[(4, 2, 2), (5, 3, 1), (7, 1, 1), (8, 0, 0)]$
比如5有[1,2,3]共3个数可用，减去2个空缺，于是有1个“额外数目”。
#3，只有一个“额外数目”为0： (8, 0, 0)。
#4，8前面的所有数中，原始下标最小的就是8。于是我们把1分配给8。
重复#2，更新后的额外数目为：$[(4, 2, 1), (5, 3, 0), (7, 1, 0)]$
此处因为8已经被分配，所以删除出去。同时1不再可用，所以剩下的“额外数目”都减少了1。
#3，此时5和7的“额外数目”都是0。我们选择较小的5继续处理。
#4，5之前的所有数中（指4和5，不包括7）原始下标最小的是4。于是我们把2分配给4。
重复#2，得到$[(5, 3, 0), (7, 1, 0)]$
此处5只剩下3可以分配，同时由于4被删除，5的空缺数也变成了1。所以5的“额外数目”依然是0。
#3和#4。将3分配给5。
重复#2，#3，#4。将6分配给7。
无解的情况
显然，任何时候，一旦出现“额外数目”小于0，则必然无解。
实现思路
先看#4，其本质就是寻找“0”到“#3得到的$i$”这个区间内的，原始下标的最小值。我们立刻想到线段树维护区间原始下标最小值。
对于#3，我们只需要维护区间“额外数目”最小值，再加上二分，找到下标的最小的$i$使得区间“额外数目”最小值为0。也就可以通过线段树实现。
接着考虑删除已经分配过的$b_i$的情况。
注意到线段树上维护的都是区间最小值，那么在分配过数之后，我们可以把其原始下标的值和“额外数目”改为无穷大。这样这个$i$就永远不会出现在后续的结果中。
最后考虑分配一个数x到$b_i$对其他$b_j$的“额外数目”的影响。
对于比$b_i$本身还大的$b_j$，其实不影响“额外数目”。因为这些$b_j$会减少一个可用的数的同时也会减少一个空缺。（最右侧）
对于比x还小的$b_j$，自然不会受到影响。因为这个值本就不可能分配给他们。（最左侧）
因此实质上只有当$b_j$介于x和$b_i$之间时，“额外数目”才会减1。因为$b_j$的可用数减少了1，但是空缺却不会减少。（中间）
但这个其实也是区间修改。因此还是可以用线段树实现。
于是，整个实现就是用线段树维护区间原始下标最小值和“额外数目”最小值，然后二分找出目标的i和x所在的位置即可。
代码
Java
C++