T1：
贪心题，考虑到无论怎么跳相同的高度用的时间相等，那么为了不被淹没，向高处最低的一座塔跳即可。 $O(n)$ 模拟判断会不会被淹即可。

T2：
如果只考虑区间和问题，我们只需要做一个前缀和，开一个 map 维护一下即可。
考虑最大值的限制：
我们可以在扫描的过程中考虑维护一个 bnd 表示可能作为答案但是还没有加入 map 中的区间左端点。如此维护：

• $a_i \gt x$ 那么清空 map 并将 bnd 设为 i + 1
• $a_i = x$ 那么加入 [bnd, i] 的前缀和信息到 map 中
• $a_i \lt x$ 那么不动

对于每个点，利用 map 查询答案即可。

该题做法不止这一个，该解法经供参考。

T3：
利用抽屉原理，则该树至多有两个叶子。
考虑一条链的情况，显然是 $2^n$。
考虑两个叶子，也就是类似 Y 字形的一棵树，在分叉前的那些点随便选，考虑分叉后的东西。
如果两个叶子深度相等，显然一个为 $1$，一个为 $2$，并且每一层的点权都相等，那么答案为：

$$2 \times 2^{\mathrm{dep}_x} $$

如果不相等，那么对于两个叶子来说，填了之后，其分叉后祖先相同个数的部分必须填 $2$，而多出来的那些随便选。

唯一的问题是，如果浅的点被赋值为了 $1$，那么会多一条边被设为 $2$。所以不妨设 $\mathrm{dep}_x \gt \mathrm{dep}_y$，则答案为：

$$(2^{\rm{dep}_x - \rm{dep}_y} + 2^{\rm{dep}_x - \rm{dep}_y - 1}) \times 2^{\rm{dep}_{lca}} $$

T4：
对于每一个排列求答案是困难的，考虑另一个思路。

对于每一种移除方式，考虑有多少种排列满足可以达成它，认为移除的位置为 $\{p_i\}$，问题转化为对每个 $p_i$ 找到一个右端点与其他区间不相等的区间 $[l_i, r_i]$。

不妨设 $n \ge p_0 \gt p_1 \gt p_2 \gt \cdots \gt p_{k - 1} \ge 1$，那么答案显然为：

$$\prod_{i = 0}^{k - 1} p_i (n - p_i - i + 1) $$

考虑递推这个式子，令 $f_{i, j}$ 表示上式在 $p_k \ge n - i + 1$ 以及 $k = i - j$ 时的取值，则考虑 $p_{k - 1}$ 是否为 $n - i + 1$，有：

$$f_{i, j} = f_{i - 1, j - 1} + (n - i + 1)(j + 1) f_{i - 1, j} $$

最后的答案为：$\sum f_{n, j}$