E

这道题是关于一种运行长度压缩的方法。将一个序列 $A$ 进行运行长度压缩得到的结果为 $\widetilde{A}$，其中 $I_A$ 是表示 $\widetilde{A}$ 的前缀和。对于每个 $j=1,2,\ldots,n$，对于所有满足 $I_{A,j-1}<i\leq I_{A,j}$ 的 $i$，它们所对应的值 $a_i$ 都相等。 对于给定两行序列 $R_1$ 和 $R_2$，我们将它们的 $I$ 序列按照顺序合并得到一个新的排序后的序列 $I$。对于每个 $j=1,2,\ldots N_1+N_2+1$，对于所有满足 $I_{j-1}<i\leq I_j$ 的 $i$，它们所对应的值 $(R_{1,i},R_{2,i})$ 都相等。因此，对于每个 $I_j$，如果 $R_{1,I_j}=R_{2,I_j}$，就将 $I_j-I_{j-1}$ 加入答案中。时间复杂度为 $O(N_1+N_2)$。

F

这道题的问题是要在一些数字里面找到第 $K$ 小的数字。这个问题可以用二分查找来解决。 我们接下来考虑一个具体的决策问题，就是给定一个浓度 $x$，我们想知道有多少杯糖水的浓度比 $x$ 小。我们可以通过计算每个糖水需要添加多少糖才能达到浓度 $x$ 来解决这个问题。对于每个糖水，我们可以计算出如果它糖含量为 $t \times \frac{x}{1 - x}$ 克，那么它的浓度恰好为 $x$。如果它的实际糖含量为 $s$ 克，则：

• 如果 $s \geq t \times \frac{x}{1 - x}$，则它会多出 $(s-t \times \frac{x}{1 - x})$ 克糖。
• 如果 $s \leq t \times \frac{x}{1 - x}$，则它会少 $(t \times \frac{x}{1 - x}-s)$ 克糖。

我们可以将这两种情况统一为“它有 $(s-t \times \frac{x}{1 - x})$ 克糖”。然后，我们可以将所有糖水中 $(s-t \times \frac{x}{1 - x})$ 排序，并根据高桥给出的浓度，用二分查找来寻找青木糖水中符合条件的数量。然后判断是否至少有 $K$ 杯糖水满足条件即可。 我们可以将这个过程重复多次，直到得到一个足够准确的答案为止。整个过程的时间复杂度是 $\mathrm{O}(X N \log M)$，其中 $X$ 是我们重复运行这个过程的次数。一般建议将 $X$ 设置为约为 $100$ 左右。