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 了一发= = 所以读题要仔细啊！！！
合唱队形
$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 容斥系数的）
题还不错，就是做法割裂开了，有点降好感诶 = =
火车管理
区间压栈，单点弹栈，区间询问栈顶
$1$、$3$ 操作一棵线段树，$2$ 操作一棵主席树。主席树存时间，得到的时间也可以作为下标查询某位置的上一个版本。
代码咕了。
wangyisong1996 给出了一个二叉树的神仙做法，待补。