一类基于笛卡尔树的排列计数DP

发表于 2025-02-18 更新于 2025-02-26 分类于算法竞赛，题阅读次数：

对于排列计数 DP 问题，一种经典的手段是插入法：从小到大插入元素。

插入法会破坏相邻项，若问题关心相邻项，则不易考虑。此时可以用并段法：按某种顺序填写数字，并考虑目前已有的连续段。

若问题关心排列数字的大小，可以从小到大插入，构造排列的过程可视为“水淹笛卡尔树”。

Luogu5999 [CEOI2016]kangaroo

题意：有个草丛排成一排，编号。

有一只袋鼠，从出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达。显然他会跳跃次。

为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。

求方案数模的结果。

，时限。

按访问顺序把编号记下，得到排列，则约束为：

。
对于，或，排列形如“波浪”。

此题中，不合法的序列可能在插入后变得合法，故不能采用插入法。

从小到大填写虑元素，观察排列的表现。已加入的元素会形成若干个连续段，这些连续段内部一定是合法的。

设表示考虑了数，形成个连续段（考虑的是以连续段为元素的有序序列，不考虑中间的空位有几个等等），内部合法，段的左右都是波谷（不包括），的方案数。

插入时，讨论如下：

当时
- 可以作为新的一段插入。若（已经插了）不能插在首，若不能插在尾。
  
  记，
- 可以合并两段。
  
  此时比已有的任一个数都要大，必然可以合成并作为波峰。
当时
- 作为新的一段插在最前面：
- 放在最前面的段的前面：
（时类似）

可以发现，每种合法的排列都恰会被计数一次。

首先显然被计数的排列都是合法的，只需证每种合法排列恰只有一种计数方式。

对于给定的合法排列，从小到大考虑其中元素，维护两侧为波谷的连续段，每次插入可以得到对应的操作。

不难发现这类似于水淹笛卡尔树并维护森林。

复杂度。

CF704B Ant Man

题意：有个元素，第个元素有五个参数。

求出一个的排列，满足，同时最小化这个排列的权值。
排列的权值为，其中的值有两种情况：
- 若，则。
- 若，则。

，时限。

令，则有

设表示考虑了前个数，形成个连续段的方案数。

加入时，讨论两侧贡献的四种情况，计算关于的贡献。

- 两侧都比自己大：自成一段。注意若 $，$ 则无法转移，此时找不到空位加入新的段。
- 两侧都比自己小：合并两段。
- 左小右大：贴在一段右侧。注意若则无法转移。
- 左大右小：贴在一段左侧。注意若则无法转移。
或

就只需考虑贴最左侧和贴最右侧的情况，和上面类似。

复杂度。

Loj#2743. 「JOI Open 2016」摩天大楼

题意对于的排列，定义其“波动度”为：

求波动度的排列数目。答案对取模。

，时限。

显然绝对值可以拆开，变成讨论相邻两个数的大小关系。但这样贡献可能有负数，求和不单调，复杂度较差。

一个使得贡献单调的技巧是分层。将排序，观察的贡献系数，是满足一个，另一个的对子的个数。

每次插入时，计算的贡献系数（显然为正）。这样的贡献是单调不降的，于是可以应用的限制。

记表示前个数，形成了个连续段，目前贡献和为，选择了个边界元素的方案数。

对于新形成的边，显然有贡献，对于未形成的边和已形成的边则无贡献。

讨论有五类：自成一段，自成一边界段，贴在段的一侧，贴在段的一侧并作为边界，连接两个段。

转移见代码。

最后就是答案。

将滚动。时间复杂度，空间复杂度。

CF1515E Phoenix and Computers

题意：给定，有个电脑排成一排。

初始时所有电脑都关机，你要按某种顺序手动开电脑，使得最终所有电脑都被开启位置。

若某电脑两侧的电脑都开机，这台电脑会立刻自动开机。不能开一个已经开了的电脑。

将手动开的电脑编号依次记下，求有多少种可能的编号序列。

答案对给定的质数取模，，时限。

设表示已开机（包括手动和自动）台，形成了个连续段，且钦定连续段间距离的情况。

对于，新开一台，可能的转移如下：

新增一段：
合并两段：
- 两侧紧贴：不合法，这样早就会触发自动开机。
- 一侧紧贴，另一侧空一位自动开机：
- 两侧各空一位自动开机：
贴在某段一侧：
- 紧贴：
- 空一位自动开机：

最终是答案。

复杂度。