AGC043D Merge Triplets

题意 ： 将 划分为 个长度为 的栈。

用如下算法生成一个排列 :

• 找出栈顶最小的（非空）栈，将栈顶加到 的末尾，并弹栈。

问有多少排列 可能被生成。

，时限 。

---

我们发现这和归并排序类似，唯一的不同之处在于各个小序列初始时可能是无序的。

这给我们一种感觉：排列 必然是近似有序的。

显然，若各个栈初始时有序，则排列 必然有序。接下来考虑栈中无序带来的影响。

不难发现，若栈中有一段数 满足 （称之为“头大”段），则一定会被连续弹出。

而且，相邻两段“连续弹出”的第一次弹出是递增的。

于是，原序列被划分为了若干长度为 的头大段，且头大段的开头递增。

观察栈中连续头大段的组成：。

又能发现， 中 的个数必不多于 的个数。

若满足上述两个条件，必然能构造出对应方案。

• 构造：对于所有 自成一栈。

  对于 其中 ，选出任一个 与其配对成栈。

  若 则可以配成 ，若 则可以配成 ，总能配对。

  对于剩余的 ，三个分别排序后成一栈。

找出了充要条件，（根据数据范围）接下来使用 DP。

先考虑若已经确定段的分布，填数的方案数。约束等价为：对于段 ，要求 。

把每个段翻转，则变为要求 恰组成前缀最大值。方案数为 。

证明 ： 考虑归纳，对于满足前 条约束的所有排列，只有 个满足第 条约束。（离散化双射）

记 表示填写了前 个数， 与 的个数差为 的方案数。

转移时枚举下一段为 即可，乘权值分别为 。

为了方便，可以将 分配到乘权值中。

复杂度为 。