Codeforces Round #740 (Div. 1)
D. Top-Notch Insertions
题意
定义插入排序过程：遍历 $i=2\sim n$，当且仅当 $a_i\lt a_{i-1}$ 时找到最小的 $j$ 满足 $a_i\lt a_j$ 然后将 $a_i$ 插入位置 $j$，用二元组 $(i,j)$ 记录。
多组数据，每组数据给定序列长度 $n$ 和排序过程的所有二元组(共 $m$ 个)，假设原序列每个值 $\in [1,n]$，求原序列的所有可能情况。
数据保证 $\sum m\le 2\times 10^5$。
题解
固定 $n$ 和二元组序列，不难发现最终结果的下标序列唯一。假定最终结果下标序列为 $p$，于是有 $a_{p_1}\le a_{p_2}\le\cdots \le a_{p_n}$。
当且仅当 $a_{p_{i-1}}$ 是在插入排序时直接插在 $a_{p_i}$ 后面时 $a_{p_{i-1}}\le a_{p_i}$ 无法取等号。
假定有 $k$ 个位置无法取等，根据简单组合数学知识，知最终答案为 ${n+n-1-k\choose n}$。
现在需要维护无法取等的 $a_{p_{i-1}}\le a_{p_i}$ 的个数，发现正向维护是十分困难的，考虑逆序维护。
最后序列共有已经排序好的 $n$ 个元素，设最后一个二元组为 $(x,y)$，则最后一个二元组取得第 $y$ 个元素一定就是当前序列得第 $y$ 个元素。
不难发现当前序列的第 $y+1$ 个元素一定无法取等，将他标记，然后删除当前序列第 $y$ 个元素，继续处理倒数第二个二元组。
于是问题转化为构造一个支持查询第 $k$ 大和删除固定元素的数据结构，显然可以线段树维护。
另外题目只保证 $\sum m$ 的范围不保证 $\sum n$ 的范围，因此需要记录被修改的位置进行复原。总时间复杂度 $O(m\log n)$。
E. Down Below
题意
给定 $n$ 个点 $m$ 条边无向图。除 $1$ 号点外每个点 $i$ 有一个怪物，玩家能力值大于 $a_i$ 才能击败怪物，击败怪物玩家能力值上升 $b_i$。
玩家从 $1$ 号点出发，每条边可以走无限次，但如果玩家上一步是 $u\to v$，则这一步不能是 $v\to u$。
玩家只有杀死第 $i$ 个点的怪物才能进入第 $i$ 个点，问玩家的最小初始能力值，使得玩家能否杀死所有怪物。数据保证每个点度数至少为 $2$。
题解
不难想到二分初始能力值，难点在于如何验证答案。
考虑维护集合 $S$，对集合 $S$ 的每个点 $u$，玩家都可以从 $1$ 号点出发，杀死 $S$ 集合每个点的怪物后回到 $u$。
考虑拓展集合 $S$，可以从集合 $S$ 的任意点 $u$ 出发，进行 $\text{dfs}$，并且不经过所有 $v\in S$ 的点。
从 $u$ 出发的可行能力值为初始能力值 $+\sum_{v\in s}b_v$。按照题目规则移动，如果路径出现环，显然这条路径的所有点可以加入 $S$。
若存在 $u,v\in S$，$u\to x,v\to x$ 是两条不相交的路径，假定 $u\to x$ 获得的能量不小于 $v\to x$ 获得的能量，则可以将路径 $u\to x\to v$ 加入 $S$。
因此每次拓展集合 $S$ 可以暴力对 $S$ 的每个点进行 $\text{dfs}$，其他每个点至多被访问一次，时间复杂度 $O(n+m)$。
$S$ 最多拓展 $O(n)$ 次，因此验证答案复杂度 $O(nm)$。总时间复杂度 $O(nm\log V)$。
