A：

限制等价于位置 $i$ 的所有可能情况平均值均大于等于整体平均值，用个双指针模拟即可。

无解情况是不存在的。

B：

$i$ 使用优惠卷而 $b$ 未使用，若想让 $i$ 的优惠卷给 $j$ 用，需要满足 $a_i-b_i<a_j-b_j$。

然后我们每次找到一个原价/优惠价的最小值，与选择使用优惠卷的物品比较，判断是否替换即可。

C：

非常好NOIP模拟赛,使我默写lct

首先考虑一个实链$x_1, \cdots, x_k$（从浅到深），容易发现$x_k$一定是这$k$个节点里最晚被操作的，其他的节点之间顺序随意。然后考虑$x_1$的父亲 $y$ 所在实链的链底 $z$，$x_1$ 一定比 $z$ 早操作。于是可以建一棵树，非链底向对应链底连边，链底向父亲链的链底连边，这样每个点在新树上的父亲的操作顺序一定比当前点早。

于是变成了这个问题：有一颗树，求有多少排列满足$P_x < P_{fa_x}$。这个问题可以简单的树形 dp 得到一个式子 $\frac{n!}{\prod size_u}$。

考虑这个问题在我们重构树上的组合意义。首先非链底节点的$size$ 都是$1$，链底节点对应的$size$是所在实链链顶在原树中的$size$。因此答案即为$\frac{n!}{\prod_{u \in S} size_u}$，其中$S$表示链顶集合，$size_u$表示在原树上的子树大小。为了维护集合$S$，可以用 lct 或 树剖的方法做到1log。这里介绍树剖的方法。

考虑每次access对于树剖上一条重链的影响是：一个前缀的链顶被清空了，然后前缀的末尾加入$S$。于是每条重链可以用一个栈维护，栈顶是浅的点，每次只会在栈顶做push和pop操作，均摊复杂度$O(n \log n)$。

D：

什么 b 玩意。

考虑对问题做如下转化：随机一个排列$P$，第$i$次操作删除$P_i$的倍数，但如果$P_i$已经被删除则不计入次数。

由期望线性性，答案是每个$P_i$被记入次数的概率之和。也就是$P_i$与其因子们，$P_i$是在排列里第一个出现的概率，也就是$\frac{1}{d_{P_i}}$，其中$d_u$是$u$的因子个数。

令$f(x) = \frac{1}{d_x}$，容易发现$f_x$是积性函数，可以线性筛，获得部分分。也可以min25/洲阁筛。总之选取你喜欢的筛子，可以得到$O(n^{1 - \varepsilon})$或$O(\frac{n^{\frac{3}{4}}}{\log n})$之类的复杂度。