UNR 1 题解

争夺圣杯

求所有 $m$，所有长度为 $m$ 的区间的 $max$ 值之和，之 $xor$ 和。

当前在某个 $i$，设 $p = \min(i - L_i, R_i - i)$, $q = \max(i - L_i, R_i - i)$，对下面这三个区间的贡献：

• $len \in [p, q]: hp_i * p$
• $len \in [1, p - 1]: hp_i * len$
• $len \in [q + 1, p + q - 1]: hp_i * (p - (len - q))$

就是加一次函数。前缀和随便做？

👇这个 sb 因为忘记取模 WA 了一发= = 所以读题要仔细啊！！！

$Code$

合唱队形

$n = m$ 时，假设总共有 $p$ 节课，当前有 $r$ 个人。那么拓展到 $r + 1$ 的概率就是 $\frac{m - r}{p}$，期望次数是 $\frac{p}{m - r}$, $ans = \sum\limits_{i = 0}^{m - 1} \frac{p}{m - i}$

设 $t_i$ 表示以第 $i$ 个人为开头的队形组成的期望时间，min-max 容斥，现在要算 $\max(t_i)$。显然答案只和课程数有关！

• $n - m + 1$ 较小时，$O(n2^{n - m + 1})$ 暴枚即可，就和 $n = m$ 一样算。
• $n - m + 1$ 较大，就是说 $m$ 比较小，可以考虑 dp：$f_{i, j, k}$ 表示到第 $i$ 个人，$i$ 前 $m$ 个人为开头的队形选择状态为 $j$，有 $k$ 个课程要教的方案数（是带 min-max 容斥系数的）

题还不错，就是做法割裂开了，有点降好感诶 = =

$Code$

火车管理

区间压栈，单点弹栈，区间询问栈顶

$1$、$3$ 操作一棵线段树，$2$ 操作一棵主席树。主席树存时间，得到的时间也可以作为下标查询某位置的上一个版本。

代码咕了。

wangyisong1996 给出了一个二叉树的神仙做法，待补。