本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 20:38:49

candies

较小值和较大值，可以看成独立。因为两个极值相等后，就再也不会变化了。那么，我们考虑二分出这 $K$ 次操作能让较小的数全增至 $L$，较大的数减至 $R$。$L\le R$ 时，答案即 $R - L$；否则，只有整个序列的总和是 $n$ 的倍数时极差为零，否则为一。

复杂度 $O(n\log V)$

rcomb

先考虑 $80$ 分的部分分。设 $f(n, i)$ 表示还剩 $n$ 张试卷，第 $i$ 张试卷的期望贡献次数。

那么有转移

$$ \begin{aligned} & f(n, 1) = \frac 1 {n-1} + f(n-1,1) \ & f(n, n) = \frac 1 {n-1} + f(n - 1, n - 1) \ & f(n, i) = \frac 2 {n-1} + \frac{i-1}{n-1} f(n-1,i-1) + \frac{n-i}{n-1} f(n-1,i) \end{aligned} $$

这个复杂度是平方的，能通过 $80$ 分。

对于这个部分分，还有一种思考方向，是设 $f(i, j)$ 表示合并完 $[i, j]$ 区间的期望代价。那么 $$f(i, j) = \sum\limits_{k=i}^j a_k + \frac{1}{j-i} \sum\limits_{k=i}^{j-1} f(i, k) + f(k + 1, j)$$

利用前缀和优化，也可以做到平方。

对于 $100$ 分的数据，考虑拆贡献。每个数到答案的贡献，是上面这个式子转移中的第一个 $\sum$。我们需要知道每个数被包含在了长度为多少的区间。

第 $k$ 个数对答案的贡献，可以考虑它往左边合并的概率。当左边有 $k - 1$ 个数时，有 $k - 1$ 种合并的可能，合并到它的概率是 $\dfrac 1 {k-1}$。右边同理，合并到它的概率是 $\dfrac 1 {n-k}$。当左右操作了一轮后，合并到它的概率增加到 $\dfrac 1 {k-2}$。我们对这个求和，就可以了。

最终的复杂度是 $O(n)$。

game

考虑一个暴力。不妨令 $x_1$ 属于 $A$，我们枚举它和哪个 $y$ 对应，就知道 $A$ 的命令。然后去掉所有可以满足 $A$ 命令的人，看看剩下的人是不是合法。这个可以做到 $O(nV)$。

然后利用 bitset 压位优化。复杂度 $O(\dfrac {nV} w)$

p.s. 这玩意儿假了

tree

我们发现用传统的 dfn 序似乎很难做这个东西。因此考虑相对不常用的欧拉序。

欧拉序上一段区间，是树上的一段路径。同时，两个端点的 LCA，就是这段路径上深度最小的点。在此题里，我们可以维护每个点到根的路径长度。那么由于边权非负，LCA 就是到根最近的那个点。

然后，操作一可以转化为子树的修改，因为修改这条边会让子树内到根的路径加上边权增量。

操作二就是查询 $u \in [s_x, e_x]$ 和 $v \in [s_y, e_y]$ 的 $dis_u + dis_v - 2dis_{c}$ 的最大值，其中 $c$ 是 $u, v$ 的 LCA。由刚才的讨论，我们知道 $c$ 就是 $u, v$ 欧拉序区间内的 $\rgmin dis$。

然后考虑操作三。注意到一个性质，即我们只会取两个端点之一。可以考虑如果不取到端点，调整到其中一个端点，路径长度不减。因此，我们就转化为子树到某个点的最远距离。这和操作二可以用相同的方法。

这个东西看起来还是有点吓人。令 $l, m, r$ 分别代表 $dis_u, dis_c, dis_v$，那么我们用线段树维护区间内 $l, m, r, l + m, m + r, l + m + r$ 的最值。这个是经典的。

然后我们考虑 $[s_x, e_x]$ 和 $[s_y, e_y]$ 的交集情况，讨论 $m$ 在左边还是右边即可。复杂度 $O(n\log n)$。