AT_arc127_e [ARC127E] Priority Queue 题解

注意到操作的是一个集合，也就是加入元素的顺序不会影响答案。因此直接钦定的加入元素时不会被删除的数和会被删除的树都是从小到大加入的，因此删除操作一定是删除最近一个加入的未被删除的的元素。

因为需要保证每次删除的数都比前面的数要大，而因为前面钦定了删除一个数，这个数必须是上一次操作刚加入的。而又因为两组序列都必须是单调递增的，因此若当前是第 $i$ 个要被删除的数，前面已经有 $j$ 个数一定不会被删除，则第 $i$ 个被删除的数的值必须严格大于 $j$。

因此考虑 dp。设 $f_{i,j}$ 表示第 $i$ 次删除操作，删除的序列最大值为 $j$，不同集合的数量。则显然有初始条件 $f_{0,0}=1$。转移枚举上一个被删除的数 $j$ 可以做到 $O(n^3)$。注意到限制条件保证了 dp 的合法状态是连续的一段，因此使用前缀和优化可以做到 $O(n^2)$ 解决问题。