有一座山，从 $0$ 高度出发（最后不一定回到起点），向上向下单位高度各需要 $t_u,t_d$ 的时间。 $m+q$ 个任务，每个任务是把物品从一个高度运到另一个高度，中途你可以任意改变方向、持有任意数量的物品。前 $m$ 个任务必须完成。对于所有 $i$ ，求额外完成后 $q$ 个任务中的前 $i$ 个，最少需要走的总时间。 $m,q\leq 2\times 10^5$ 。

题解

显然我们要走到所有任务涉及到的最高点，向上的过程中就可以完成所有向上的任务，因此只需要考虑向下的任务。

一个显然的方案是向下的任务都在向下的过程中完成，向下一直走到所有向下的任务涉及的最低点。但这不一定最优；考虑最后一段（ $u_{-1}$ 到 $d_{-1}$ ）和倒数第二段（ $u_{-2}$ 到 $d_{-2}$ ）向下的任务（如果多个任务区间重叠，那合并成一段），我既可以选择到达 $d_{-2}$ 后花费 $(d_{-2}-d_{-1}) t_d$ 继续往下走，也可以选择在上升过程中就完成最后一段任务（ $0 \to u_{-1} \to d_{-1} \to u_{-1} \to \text{继续向上}$ ），花费 $(u_{-1}-d_{-1}) (t_u+t_d)$ 。

因此我们考虑到了顶点之后向下走多少；每多走没被覆盖的一格，就额外多花费 $t_d$ 的时间；每多走被覆盖的一格，就额外少花费 $t_u$ 的时间。

区间覆盖、查询最小前缀和。

H. Harmony of Skills

题意

给定一棵无根树，点有点权。多次询问，给定一个点，询问若以其为根，有多少对子树是同构的。 $n\leq 2\times 10^5$ 。

题解

先通过换根 DP 求出所有子树的哈希。接着 DFS，每次走一条边只会改变一个子树，边搜索边维护可以求出所有点为根时的答案。

J. Jester's Scroll

题意

通信题。

给定序列 $a,b,c$ ，保证 $a_i+b_i+c_i$ 是定值；把 $a$ 中连续的相同数压缩成一个数得到 $a'$ ， $b,c$ 同理。这个序列会给到程序甲，程序甲可以传递 $n$ 个 bit 给程序乙。程序乙会收到 $a',b',c'$ 和甲传递的 $n$ 个 bit，求出一个可能的 $a,b,c$ （即只需满足 $a_i+b_i+c_i$ 是定值、压缩后得到的序列与乙收到的相同、长度为 $n$ ；不需要是原序列。显然如果忽略计算量、乙可以不借助甲传递的信息）。 $n\leq 30000$ 。另有 $a_i=0$ 且只能传输 1-bit 的子任务。

题解

考虑假如乙已经复原出 $a,b,c$ 的一个前缀，现在他要决定序列的下一个元素分别是否取 $a',b',c'$ 中的下一个元素、还是重复当前元素。分析需要考虑的选项：

首先 $a',b',c'$ 中的下一个元素要存在；
其次新的元素的和要与当前元素的和相同；
最后，三个数全部重复的选择可以直接抛弃，只在 $a',b',c'$ 都被取空后再用这个选择。简单讨论，发现每个位置至多有 $2$ 种选择。约定好找到选择的方式（顺序），甲只需要找到 $a,b,c$ 在每个（不是全部重复上一个数的）位置具体选了哪种，传递给乙，乙复刻甲的选择即可。

$a_i=0$ 时，可能的选择只有一个，从而不需要传递信息。

下落时找到对应列的最高有方块行号、转化成高度、计算砖块掉到什么高度、在 set 里相应插入行号、在行上加方块数、消除时移除 set 内元素并更新映射

（L 和 M 是队友写的）