这是本文档旧的修订版！
Codeforces Round #732 (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)$。
