不是所有的题我都做出来或者补出来了，因为我就是个废物，我就是个废物，我就是个废物啊！

独立完成 ABCDE。已完成 ABCDEF。

本题题解同步发表于洛谷题解区。（没过）

考虑没有前向边的搜索树。

全部非树边均为祖先关系，即为返祖边，无横叉边，使用任意一棵 dfs 树即可。

均非祖先关系，即为横叉边，无返祖边，即可使用图的 bfs 树。

注意两棵树不一定不同。

独立完成 ABCD。已全部完成。

如果面包长度之和小于原长度，则新增一块面包补全长度。

接下来考虑建出面包合并树，树上的每一个节点的值代表目前面包的长度。合并树上非叶节点的值之和即为答案。

贪心，每一次从优先队列取最小的两个面包合并，然后又把合并后的面包塞回优先队列。

时间复杂度 $O(n\log n)$。

给我一种在抄题解的感觉，不过作为一道树的计数+区间 dp 题还是很妙的。

设 $f_{l,r}$ 代表 $[l,r]$ 能构成以 $l$ 为根的子树个数，答案即为 $f_{1,n}$。

发现它不好转移，于是再设 $g_{l,r}$，$g$ 在 $f$ 的要求上更高，要求 $r+1$ 能够以 $l$ 的直接儿子的形式加入子树 $l$。

$f$ 的转移是

$g$ 的转移要求 $a_{i+1}<a_{r+1}$，其余转移同理。

时间复杂度 $O(n^3)$。

有人这题拖了一个月，我不说是谁。

根据小学奥数，将一个数拆成若干个数使乘积最大，尽量多拆 $3$，少拆 $2$，不能拆 $1$。

按以上规则，$n=70$ 时选法不超过 $2\times 10^{11}$。以下令选法数为 $m$。

考虑把所有数分成两半，使两边的选法数尽量相近。以下令暴力得到的两个数组分别为 $a,b$，求的是 $a_i\oplus b_j$ 的第 $k$ 大值。

朴素想法是二分答案，但因为这种做法有二分的 $\log$，所以复杂度是 $O(\sqrt m\log^2V)$ 的。

用类似于线段树二分的方案，维护目前的答案和所有 $b_j$ 与目前答案的异或和，还有它们在 Trie 树上的节点。优化复杂度至 $O(\sqrt m \log V)$。注意目前为空树的情况，所以建议把节点从 $1$ 开始标号。

字典树空间要开 $3\times 10^7$！！！！！

说到为什么今天要做出这题，就是因为自己中考后一次题都没讲过，想讲一下，之前挑战的题全都没搞懂，只有这题懂了，遂完成代码。

独立完成 ABCD，已完成 ABCDEFG。

开局一眼丁真二维线段树，但这不能用于矩阵区间的修改。只能前缀和修改法。

注意到每一个操作 $2$ 都会使前面的操作效果消失。考虑主席树维护每一次修改。因为我不会区修的主席树，遂写了一个差分的做法（每一个版本建两颗树）。查询最后一次对应的 $2$ 操作之后的答案即可，具体而言是两个前缀和相减。

时空复杂度均为 $O(n\log n)$。

把所有左端点相同的操作称为同组操作。同组操作全部运行完之后的唯一变化就是最后一个元素被交换到了第 $l$ 个位置，其余的顺次往后。

$[l,r]$ 中同组操作没有运行完的最多只会出现两次，且运行完的都在一起。于是统一处理所有运行完的，其余两个可以单独处理。

代码实现最好标注每一组操作的实际运行情况。时间复杂度 $O(n)$。

以前 q1uple 分享过 Ex。独立完成 ABCDE。已完成 ABCDEFEx。

考虑求 $\gcd$ 时把整个数组二维差分，变成在两个序列上查询 $\gcd$。

具体而言查询差分后数组的 $\gcd(\text{abs})$。还要和差分的第一个元素取 $\gcd$。

之前看过 Ex 的大概做法。独立完成 ABDF，已完成 ABCDEF。

啥时候连 E 都这么难理解了。

容易发现确定任何一个序列中的元素，整个序列就确定了下来。

枚举在某一个位置填入一关键元素，推出 $a_1$ 的值并在 map 的相应位置加 $1$。

答案为 map 的最大数，建议使用 unordered_map 可以使程序运行时间减少 $80\%$ 以上。

Ex 是我们的作业题。独立完成 ABCD。已完成 ABCDE。

当时看到是个 $2000+$ 有些不敢做，不过挺简单啊！

对于每一个数 $i\in [1,m]$，枚举有 $\ge k$ 个数 $\le i$ 的概率。

一个需要注意的地方是我们没有钦定是哪些数 $\le i$，所以需要枚举所有数的情况，包括对于每一个 $x\ge k$，有 $x$ 个数 $\ge i$ 的概率。

容斥的思路类似于 ABC423F Loud Cicada，不同的地方在于本题所有相同 $x$ 的容斥内容均一致。

然后差分即可！