联测题解
__ryp__
·
·
个人记录
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 欧拉序区间内的 \argmin 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)。