AtCoder Beginner Contest 217 题解
A~C
略。
D
用一个 set 维护砍掉了哪些点。
查询时直接 lower_bound 即可。
E
用两个数据结构维护。这里可以用 priority_queue 和 queue（当然 multiset 和 vector 之类的也行）。
操作 1：加入 queue。
操作 2：若 priority_queue 不为空，那么输出队头并弹出；否则输出 queue 队头并弹出；
操作 3：将 queue 中所有元素加入 priority_queue 中，并将 queue 清空。
F
赛时 naive 了，被一种特殊情况限制住了思路 ( exttt{/kk})
设 (dp_{i,j}) 表示将区间 ([i,j]) 覆盖完的方案数。
转移枚举一个点 (k)，让 (k) 和 (j) 配对，那么就把区间分成了 ([i,k-1]) 和 ([k+1,j-1]) 两段，方案数就是 (dp_{i,k-1} imes dp_{k+1,j-1} imesinom{frac{j-i+1}{2}}{frac{k-i}{2}})。组合数可以这样理解：区间 ([i,j]) 总共需要进行 (frac{j-i+1}{2}) 次配对，其中有 (frac{k-i}{2}) 次是在前面一段，之所以不需要再乘阶乘是因为两段内部的顺序已经计算过了。
答案即为 (dp_{1,2n})。
G
设 (dp_{i,j}) 表示 (1sim i) 分成 (j) 段的方案数。
转移：(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j} imes(j-lfloorfrac{i-1}{m} floor))。
前面的是 (i) 单独分一段的贡献，后面是 (i) 加入前面的一组的贡献。因为前 (i-1) 个数中和 (i) 在(mod m) 下同余的有 (lfloorfrac{i-1}{m} floor) 个，而它们都不在同一个组，所以系数就为 (j-lfloorfrac{i-1}{m} floor)。
H
咕咕咕