本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-24 21:00:21

本来想只开一篇专栏，然而发现内容爆多，故决定之后每周开一篇记录。

09.24 排序分析

当只关心相对大小，而不关心实际值时，可将所有数离散化，得到值域为数字个数的新序列。

更进一步地，若只关心每个数与 $x$ 的相对大小，则可将其离散化为 $[a_i\ge x]$，得到一个 $01$ 序列，从而更容易分析其变化。

[AGC006D] Median Pyramid Hard

题意

给出一个长为 $2n-1$ 的排列，每轮依次取相邻三个并求中位数，得到长度减少 $2$ 的序列，如此进行 $(n-1)$ 轮，求最终得到的数。$n\le 10^5$。

题解

先二分答案，判断答案是否不小于 $x$，这时只关心数与 $x$ 的相对大小，因此只需对 $01$ 序列操作，判断最后剩下的数是否为 $1$。手推发现若有 $11$，则其可以一直向上延伸，直到某个位置消失，$00$ 也是类似的。同时若有 $101$，操作后 $0$ 上面是 $1$，因此 $11010$ 会变成 $110$，在边上仍然存在 $11$。

总结一下上述规律，发现离正中间最近的 $00$ 或 $11$ 会延伸得最高，之后与靠近中间的一侧不断合并，从而贡献到最顶端。同时由于序列长度是奇数，若两边最近距离相同，则它们的值也是相同的，两种值的最近距离一定不同。因此判断时找离中间最近的 $00$ 或 $11$ 即可，若无则说明整个序列是交替的，需特判为 $[a_1\ge x]$。时间复杂度 $O(n\log n)$。

考虑优化，发现只关心以每个 $x$ 为分界点时 $00$ 和 $11$ 到中间的最近距离。因此可以正序枚举 $x$，这时整个序列会从全 $1$ 逐渐变成全 $0$，容易维护每个时刻 $00$ 的最近距离。同理倒序枚举 $x$ 即可求得 $11$ 的最近距离，之后枚举答案并 check 即可，时间复杂度 $O(n)$，提交记录。

P4375 [USACO18OPEN] Out of Sorts G

题意

给定序列 $a$，每轮先后进行顺逆冒泡排序各一次，求多少轮后序列不降。$n\le 10^5$。

Bonus：每轮进行顺序冒泡排序 $x$ 次，逆序冒泡排序 $y$ 次，原题为 $x=y=1$。

题解（Bonus）

先将原序列离散化，值相同的认为靠前的更小，这样能转化成一个排列。之后枚举每个值域分界点 $p\in[0,n]$，将原序列转化成 $b_i=[a_i\gt p]$ 的 $01$ 序列，则当且仅当所有 $01$ 序列均不降时原序列不降，因此对 $(n+1)$ 个 $01$ 序列的答案取最大值即可。

对于一个 $01$ 序列，手推可以发现顺序操作会将每个 $1$ 连续段的最后一个扔到下一个 $1$ 连续段开头，逆序是类似的。由于相同的 $01$ 值不作区分，可以认为顺序操作将第一个 $1$ 扔到结尾，逆序操作将最后一个 $0$ 扔到开头，求多少轮操作后 $0$ 是一段前缀。图形化的理解方式是从坐标系原点开始，经过 $0,1$ 时分别令 $x,y$ 增加 $1$，形成一段折线。关注折线下方的图形，则将 $1$ 扔到结尾会删掉最下面一行，将 $0$ 扔到开头会删掉最后一列，折线下方被删空时序列不降。

单轮操作只需要维护两个指针 $p,q$，初始 $p=0,q=n+1$，每轮 $p$ 向后扫过 $x$ 个 $1$，$q$ 向前扫过 $y$ 个 $0$，若 $p\gt q$ 则停止并返回当前轮数。考虑将这个过程形式化，设 $A_i$ 表示 $i$ 及之前 $1$ 的个数，$B_i$ 表示 $i$ 及之后 $0$ 的个数，则所求即 $\max_{i=0}^n\min(\lceil \frac {A_i}x\rceil,\lceil \frac{B_{i+1}}y\rceil)$，含义即为每对 $i\lt j,b_i=1,b_j=0$ 的 $(i,j)$ 均需要交换前后顺序，对它们需要的轮数取最大值。

此时从小到大枚举 $p$，每次只会将一个 $1$ 变成 $0$，这会对 $A$ 的一段后缀以及 $B$ 的一段前缀进行修改，两个树状数组即可维护。同时由于 $A$ 不降且 $B$ 不增，找到 $\lceil \frac {A_i}x\rceil\le\lceil \frac{B_{i+1}}y\rceil$ 的最后一个位置 $t$ 后，只需要对 $i=t$ 和 $i=t+1$ 取最大值即可。而修改是减少 $A$ 且增加 $B$，因此 $t$ 的位置也是不降的，每次更新后尝试向后移动 $t$ 即可，时间复杂度 $O(n\log n)$，提交记录。

事实上，对于每个分界点 $p$ 来说，目标是令其前面全为 $0$，后面全为 $1$，因此在 $x=y$ 时（比如原题的 $x=y=1$），每次就会将 $p$ 前面的 $x$ 个 $1$ 扔到后面，之后将 $y=x$ 个 $0$ 扔回来，答案就是 $\lceil \frac {\max_{p} \sum_{i=1}^p [a_i>p]} x\rceil$。然而 $x\ne y$ 时进出不相等，比如 $y< x$ 时扔到后面 $x$ 个 $1$，然而递补过来的 $(x-y)$ 个值不确定，因此不能这么做。

09.24 思考题 区间排序

我说这才是排序分析。

有一个长为 $n$ 的序列 $a$，给出操作 $s(l,r)$，表示对序列 $a$ 该区间升序排序，称一个排序过程合法当且仅当所有可能的序列 $a$ 在经过这些操作后均不降。

• $a_i$ 的取值只要不唯一，排序过程合法性与值域无关。

对于同样的排序过程，序列合法本质上是 $O(n)$ 个 $01$ 串均合法，找到瓶颈所在的 $01$ 串即可构造出取值只有两种的等价序列。

• 若限制 $r-l+1\le 2$，合法排序过程的最小步数量级为 $O(n^2)$。

显然每次最多只能减少一个逆序对，构造冒泡排序过程可以达到下界 $\frac{n(n-1)}2$。

• 若限制 $r-l+1\le 3$，合法排序过程的最小步数？

每次最多减少 $3$ 个逆序对，因此有下界 $\lceil\frac{n(n-1)}6\rceil$，当然这个下界很可能是达不到的。同时严格优于限制为 $2$ 的情况，有上界 $\frac {n(n-1)}2$。直接用长为 $3$ 的区间构造冒泡排序可以做到大概 $\frac {n(n-1)}4$，因为可以将两个长为 $2$ 的操作合并成一个。

还有一种构造是每轮不重复地覆盖整个序列，从而让整个序列变得合法，LCA 课上提了一种做法，据说是 $\frac {2n(n-1)}9$ 的，然而写了程序爆搜 $9$ 以内的循环节并没有找到低于 $\frac {n(n-1)}3$ 的合法覆盖方式，先不管了。

• 验证排序过程合法性时，只验证降序合法是否能直接说明合法？

是可以的，仍然考虑 $01$ 串，定义 $p$ 不劣于 $q$ 当且仅当两者长度相同，$1$ 的个数相同，且对于每个相同排名的 $1$，在 $p$ 里的位置均不比在 $q$ 里靠前。这个定义下并非任意两串都能分出优劣（比如 $0110$ 和 $1001$），但这是具有传递性的，且升序合法状态比其他串都不劣，降序串比其他串都劣。

更进一步地，每个串每次操作都不会变劣，且若 $p$ 不劣于 $q$，两者均经过某操作 $s(l,r)$ 后得到的 $p',q'$ 一定满足 $p'$ 不劣于 $q'$，证明只需要考虑两者该区间内 $1$ 的变化即可。由此无论操作序列如何，降序串一直是最劣的，因此降序串合法就能说明原串合法。再结合第一条即可说明该结论。

• 哪些常见排序算法可以描述成上述区间排序过程？

冒泡排序，且满足 $r-l+1\le 2$。

插入排序，方式是依次进行 $i\in[1,n]$ 的所有 $l=1,r=i$。

归并排序，先递归到 $[l,mid],[mid+1,r]$，再进行 $s(l,r)$ 的归并过程。

[AGC001F] Wide Swap

题意

给出长为 $n$ 的排列 $p$，可进行任意次交换 $p_i,p_j$ 的操作，但必须满足 $\left|i-j\right|\ge k$ 且 $\left| p_i-p_j\right|=1$，求字典序最小的最终排列。$n\le 5\times 10^5$。

题解

有值限制的任意交换太困难了，考虑转化为逆排列 $q_{p_i}=i$，并在 $q$ 上进行交换。这时限制变为 $\left|q_i-q_j\right|\ge k$ 且 $\left| i-j\right|=1$，第二个限制就是相邻了，这样看起来就好了很多。同时字典序最小的 $p$ 对应的是倒序字典序最大的 $q$，证明考虑首先要让 $q_x=1$ 的 $x$ 尽可能小，也就是从小到大依次尽可能靠前，那么从后往前依次填尽可能大的数就是对的。

由于只能邻项交换，考虑初始序列 $q$ 和最终序列 $r$，若 $q$ 中 $x$ 在 $y$ 前面，$r$ 中 $x$ 在 $y$ 后面，则交换过程中一定直接交换过 $x,y$ 两个值，因此要求 $\left|x-y\right|\ge k$。每一对值均有该限制，存在限制无法满足的最终序列一定操作不出来。

若能证明满足限制的最终序列 $r$ 一定能操作出来，那么就可以这样刻画合法序列。考虑构造 $q$ 变成 $r$ 的操作，方式是依次将 $q$ 的每一位变成与 $r$ 相同，若目前不同则从后面依次交换过来，然后忽略第一位继续向后构造。若过程中出现无法交换的情况，此时这两个值的先后顺序一定需发生变化，这说明 $r$ 无法满足该限制，而这是不可能发生的。因此一定能构造出 $r$。

将该限制重写回 $p$，则对于所有 $\left|i-j\right|\lt k$ 的下标 $i,j$，若初始时 $p_i<p_j$，则最终也一定有 $p_i\lt p_j$，求字典序最小的 $p$。这是一些偏序限制，然而解决方式并非由 $i$ 向 $j$ 连边，再进行取最小值的拓扑；而是应该建反向边，并进行取最大值的拓扑，并依次为其赋上从大到小的值。比如 $n=3$ 时只有 $(3,1)$ 的限制就能卡掉。然而本题的边比较特殊，错误方式也能过。

这样我们得到了 $O(n^2)$ 的拓扑排序做法，优化可以使用线段树隐式建图，考虑 $i$ 的入度为零表现为只考虑未处理的点时，$i$ 在 $p$ 的 $(i-k,i+k)$ 区间内为最大值。因此用线段树维护该过程，用堆维护目前入度为 $0$ 的所有点，每次取出堆顶 $i$ 时只需要查看 $(i-k,i)$ 和 $(i,i+k)$ 两区间内是否有点入度变为 $0$ 即可。时间复杂度 $O(n\log n)$，提交记录。

另一种考虑方式是类似前置，直接找到倒序字典序最大的 $q$，最后再转回原排列。考虑直接任取一个 $q_i-q_{i+1}\ge k$ 并将其交换，直到不存在这样的 $i$，并证明这样一定能操作到最优解。

设上述操作得到序列 $r$，若要继续操作使其更优，一定要进行 $q_i\lt q_{i+1}$ 的交换，且只有向前与最近的 $q_p\gt q_{i+1}$ 交换才会变得更优。然而此时 $q_{p+1}<q_{i+1}$，且 $q_p-q_{i+1}\ge k$，从而一定有 $q_p-q_{p+1}\ge k$，与前面的假设矛盾。因此无法操作的序列一定最优，同时最优解唯一，从而任选这样的位置操作均能得到最优解。

因此只进行 $q_i-q_{i+1}\ge k$ 的操作即可，同前置可用冒泡排序维护该过程，即每次从头到尾试图进行合法操作，从而确定 $r_n$ 的值，再对前 $n-1$ 个数进行操作。容易分析出这样放到结尾的一定是能到结尾的最大值，时间复杂度 $O(n^2)$。

优化考虑前置中区间排序状物的排序算法，其中只有归并排序是 $O(n\log n)$ 的，因此尝试用归并排序代替冒泡排序，每次将左右两边归并起来，从后往前确定值。此时右边可以直接放，左边的 $x$ 要放必须越过右边未放的所有元素。

该限制看似困难，然而只要右边还有比 $x$ 大的数 $y$，此时就一定不会放 $x$，同上面的证明过程，$x$ 跳过 $y$ 后只有再跳过比 $x$ 小的元素才能更优，然而这不可能存在，否则右边还能操作。综上 $x$ 只在比剩余最大值 $y$ 大时会被放，且需满足 $x-k\ge y$，预处理右边前缀最大值即可快速查询 $y$。总时间复杂度 $O(n\log n)$，常数比上种做法小得多，提交记录。

09.26 括号序列

其实不止是括号序列，一些类似匹配消除的序列也可以归入此类。

P9753 消消乐

参见【做题记录】P9753 + CF1223F，有补充，此处略过不表。

P7323 [WC2021] 括号路径

题意

给出一张 $n$ 个点 $2m$ 条边的有向图，输入的 $m$ 组 $(u,v,w)$ 同时表示 $(u,v,w)$ 和 $(v,u,-w)$ 两条边，正负分别表示该种的左右括号。求有多少组 $x\lt y$ 满足存在一条边权为合法括号序列的从 $x$ 到 $y$ 的路径。$n\le 3\times 10^5,m\le 6\times 10^5$。

题解

注意到合法性是可以传递的，即 $(x,y)$ 和 $(y,z)$ 均合法即有 $(x,z)$ 合法，这对应合法括号序列的拼接。同时合法性是对称的，即若 $(x,y)$ 间存在合法路径，走它们的反向边即为 $(y,x)$ 间的合法路径。于是可以对所有点划分集合，使得每个集合内两两间均有合法路径，答案即 $\sum {c\choose 2}$。

可以使用并查集维护集合，上述拼接的合并是自然的，还需要实现在外面套一层括号的合并，这需要对每个集合维护所有入边，并在合并集合时将相同种类入边起点合并起来。用 map + 启发式合并可以做到常数不大的 $O(m\log ^2m)$，用线段树合并可以做到 $O(m\log k)$，后者跑得快一些。

P11236 [KTSC 2024 R1] 水果游戏

题意

给定序列 $a$，操作可以将序列中相邻相等的两个 $x$ 替换为一个 $x+1$。要求支持单点修改，查询某区间任意操作后最大值的最大值。$n,q\le 10^5,a_i,x\le 10$。

题解

先考虑不带修的情况，虽然这和正解没啥关系。可以想到只关注那些能合成单个数的区间 $(l,r,x)$，区间询问时找该区间完全包含的 $x$ 最大值即可。现在需要说明这样的区间个数有限，并找出所有的这类区间。将其转化为 $b_i=2^{a_i}$，则区间能合成单个数需要能分成两个和为 $2^{k-1}$ 的合法区间。

显然有数量上界 $O(nV)$，固定左端点即可。预处理可以倒着扫，每次二分出对应的右端点 $r$ 和中点 $m$，还要求 $m$ 开始的 $2^{k-1}$ 合法，复杂度容易做到 $O(nV\log n)$，用双指针可能也能做到 $O(nV)$。对区间贡献容易矩形加扫描线，强制在线也能可持久化，反正能做，时间复杂度 $O(nV\log n)$。

事实上即使没有值域限制，也有数量上界 $O(n\log n)$，虽然这和正解也没关系。考虑分治，每次取中点 $mid$，只考虑 $l\le mid\lt r$ 的所有区间。枚举较长一侧的长度，则只有唯一的 $2^k$ 与之对应，同时总共只有 $O(n\log n)$ 的枚举量，因此合法区间数量至多是 $O(n\log n)$ 级别的。

再考虑带修情况，然后发现上面的东西根本拓展不了，需要其他性质。考虑合并过程中若出现 $x_i\lt x_{i-1},x_{i+1}$，则 $x_i$ 之后无法再合并，可将其删去并将序列分成两半。同样地，将 $y$ 个 $x$ 的相等连续段缩成 $(x,y)$ 后再考虑，若有 $x_i\lt x_{i-1},x_{i+1}$，讨论是否有 $2^{\min(x_{i-1},x_{i+1})}\mid y$，若有则将其强制合并成较小的，贡献到对应的 $y$ 里并将其删去；否则其同样无法被跨过，然而此时还可能分别向两边贡献，可改为 $(x,y),(\infin,0),(x,y)$ 三个元素，使其能向两边贡献。

注意到序列不能再缩时能以 $\infin$ 为分界线分成若干单峰序列，每部分之间独立，且只有两边的序列会改变。这可以作为区间信息维护到线段树上，从而支持单点修改和区间查询。需要维护的有区间能合成的最大值 $w$，区间是否只有一个单峰序列以及左右两侧的单峰序列。

合并时 $w$ 先对两儿子取较大值，再将中间的两个单峰序列合并，并将新序列能形成的最大值贡献给 $w$。合并方式是依次将右边的 $(x,y)$ 放到左边结尾，先不断进行删除操作直到结尾 $x_i\ge x$，再将其贡献到 $y_i$ 或直接加入，左序列单增时也可以直接加入。统计能合成的最大值只需要从两边依次贡献到中间即可。细节较多，单次合并的复杂度为 $O(v)$，总时间复杂度 $O((n+q)v\log n)$，空间复杂度 $O(nv)$，可以通过。

CF1685C Bring Balance

题意

给出一个左右括号各 $n$ 个的序列，操作可选择区间按下标翻转，求使该序列平衡的最小操作次数，构造方案。$\sum n\le 2\times 10^5$。

题解

扔到折线上考虑，观察区间翻转会造成什么影响，发现是折线中心对称，即 $\forall i\in[l-1,r],a'i=a{l-1}+a_r-a_{l-1+r-i}$。因此感性理解会选择尽可能大的 $a_{l-1},a_r$，考虑全局最大值 $a_p$，若选择 $[1,p]$ 和 $[p+1,r]$ 两次操作，每个元素都会变成 $a_p-a_t\ge 0$，序列必定合法，所以操作次数不超过 $2$。

操作次数为 $0$ 容易判断。而操作次数为 $1$ 只能操作一次，又必须覆盖所有初始为负的位置。设最靠前的负位置为 $x$，最靠后的负位置为 $y$，则取 $x$ 之前的前缀最大值和 $y$ 之后的后缀最大值操作一定最优，检查是否能让所有负位置变为非负即可。复杂度 $O(n)$。

CF1458D Flip and Reverse

题意

给出一个 01 串，每次操作可选择一个 01 数量相等的区间，将其先按值取反再按下标翻转，求任意操作后能得到的字典序最小串。$\sum n\le 5\times 10^5$。

题解

仍然扔到折线上，操作相当于折线左右对称。观察考虑后发现这不会改变值上的连边情况，即每种 $(a_i,a_{i+1})$ 都是不变的。另外若用相同 $(a_i,a_{i+1})$ 构造折线，则一定能用题目操作得到。于是就变成安排边的顺序，使得字典序最小。

记录每种边的数量，直接求字典序最小的欧拉路径即可。然而这题的边很特殊，可以用贪心求。具体地，边的方向甚至都不重要，只要安排了对应数量的边，最终方向也一定是对的。因此每次看是否能到 $x-1$，若存在 $(x-1,x)$ 且 $(x,x+1)$ 不存在或 $(x-1,x)$ 有超过一条，就可以直接走到 $x-1$，否则走到 $x+1$。时间复杂度 $O(n)$。

CF1503F Balance the Cards

大概是推一推结论之后建模成平面图上将某个结构缩成单点，维护这个过程求解。太困难遂弃之。

彩色括号？

题意

给出一个括号序列，有红绿蓝三种颜色，可进行单点修改操作，要求最终红绿和绿蓝子序列均为合法括号序列，求最小操作次数。$n\le 5000$，Bonus：$n\le 10^5$。似乎没有出处。

题解

考虑对单个序列如何令其合法，发现只会修改最前的右括号和最后的左括号，且一定是单个修改同种若干次，再修改若干对括号，这是因为要求前缀和非负，而这种修改得到的前缀和最大。

然而三色括号很难处理，考虑通过枚举某些量的方式简化，注意到绿色在两边都有，若枚举绿色的单个修改情况，就可以推出其他两种颜色的单个修改情况，并根据上述结论得到一个新序列，满足红绿和绿蓝子序列中的左右括号数量平衡。之后再枚举绿色修改的括号对数 $c$，同样也是从两边开始修改，之后需要用红蓝两色的成对修改使得两串合法，显然 $c$ 递增时两边需要的修改数均不降，可以使用双指针维护两边需要的次数。枚举量是 $O(n^2)$ 的，细节实现没想好。

Bonus 应该是减少一维枚举，但没想。

09.26 思考题 介值定理

介值定理表明，闭区间上的连续函数可以取到最大值和最小值之间的任意值。

在 OI 中，单次变化量为 $1$ 的函数可以认为是连续的，一定能取到最大值和最小值之间的任意整数值。OI 中运用时可以使用二分，注意这里不需要单调性，只要时刻保证 $f(l)$ 和 $f(r)$ 在所求值 $y$ 两侧即可。

应用上比如说要求 $g(x)\times g(x+1)<0$ 的某个位置，可以通过某种方式求出 $g$ 的全局最大值和最小值，若异号则一定存在某个位置两侧的符号不同，二分并时刻保证左右端点不相同即可。可参见 25.02-MX-D3T1。

有一些例子，比如给出若干根粗细相同，密度均匀但质量不同的棍，可以至多切两刀，再将其分成两个集合，要求同时均分体积和质量。考虑将其首尾相接拼成环，则环的任意直径都能均分体积，这时逐渐改变直径的角度，两侧的质量差会连续变化，且旋转 $180$ 度后质量差是原来的相反数，根据介值定理一定存在一个时刻均分质量，二分找到该时刻并从对应位置切开即可。

还有一种方式是将 $(v,m)$ 向量相加画在二维平面上，现要求其过 $(\frac v2,\frac m2)$ 点，从而该点两侧的集合满足限制。此时只要有相邻向量的平行四边形包含该点，就可以通过沿该点的投影切开两向量，再通过平移经过该点。由于按斜率升序和降序排序分别在该点上下两侧，因此不断邻项交换斜率逆序对，总存在一个时刻能包含该点，实现上可以二分冒泡排序的过程？反正这种题实现也不重要不管了。

等分平面点集

给定二维平面内 $n$ 个点，其互不重合且三点不共线。所有问题中线上的点均可自由决定归属。

• 对 $a,b,c$ 取遍任意实数的所有直线 $ax+by+c=0$，它们上方的点集种类数是什么级别的？

考虑对于所有直线，均向上平移直到碰到点，之后令其绕该点顺时针旋转，直到碰到另一个点。整个过程中上方点集没有改变，而最终找到了一条等价的过两点的直线。由于过两点的直线只有 $O(n^2)$ 条，本质不同的上方点集也不超过 $O(n^2) $ 种。

• 给定点 $(x,y)$，从过该点的直线中找一条，使得其两侧的点数差不超过 $1$。

介值定理，两侧交换，差变为相反数，一定存在零点。

• 找两条相交的直线，使得四个部分中的点数极差不超过 $1$。

先任取一条平分所有点的直线，再找一条与其相交的直线同时平分两部分。方式是考虑两条直线的夹角 $\theta$，再令其平分上方的点，此时下方的点数差随 $\theta$ 连续变化，这个画图分析一下线碰到点的时刻即可。由此根据介值定理即可确定出同时平分两部分的直线。

• 找三条共点的直线，使得六个部分中的点数极差不超过 $1$。

先找到与横轴夹角为 $\theta_1$ 的平分所有点的直线，再用上面的方式找出同时将两部分划分为 $1:2$ 的直线，夹角为 $\theta_2$，最后再将其中一个 $2$ 平分，夹角为 $\theta_3$。可以说明此时另一个 $2$ 两侧的点数差随着 $\theta_1$ 的变化是连续变化的，且 $\theta_1$ 增大 $180$ 度时取相反数，因此同样可以根据介值定理确定解。

另外，更多条直线的情况就不能再这么做了，因为上面第三维用到了第一维的自由度，之后就没法确定了，总之比较抽象，但是思想值得学习。

9.28 序列相关

• 区间最值

区间最值可用笛卡尔树刻画，$[l,r]$ 的区间最值为笛卡尔树上 $l,r$ 两点 LCA 的值。有时一类关于区间最值，尤其是最近的比自己大 / 小的位置有关的问题可以考虑笛卡尔树。

CF1748E Yet Another Array Counting Problem

题意

给出序列 $a$，求值域为 $[1,m]$，且所有子区间的最靠左最大值位置均与 $a$ 相同的序列 $b$ 数量。多组数据，取模，$\sum nm\le 10^6$。

题解

对序列建出大根笛卡尔树，子区间最靠左最大值位置即两端点 LCA，因此要求 $b$ 序列的笛卡尔树结构与 $a$ 相同。在 $a$ 的笛卡尔树上进行树形 DP，设 $f_{u,i}$ 表示 $u$ 点值为 $i$ 时子树内方案数，转移为 $f_{u,i}=(\sum_{j=1}^{i-1}f_{lc_u,j})(\sum_{j=1}^i f_{rc_u,j})$，用前缀和优化即可做到 $O(nm)$。

[ABC262Ex] Max Limited Sequence

题意

给出若干限制 $l,r,x$，表示要求 $a$ 序列的 $[l,r]$ 区间最大值为 $x$。求值域在 $[0,m]$ 内的合法 $a$ 序列数量。取模，$n,q\le 2\times 10^5,m\lt mod=998244353$。

题解

这是 LCA 所说没那么板的区间最值题。要求形如区间均不超过 $x$，且至少存在一个 $a_i=x$，此时每个位置都有一个最低下界 $b_i$，这可以随便用数据结构求出。之后再考虑区间存在 $x$ 的限制。注意到区间 $b_i\le x$，不存在超过 $x$ 的 $b_i$，因此只考虑 $b_i=x$ 的位置即可。

所以将位置按 $b_i$，限制按 $x$ 分类，对这些位置和限制一起算方案数，限制形如某些区间内至少有一个取到上界，不取到上界的 $x$ 种值是等价的。这就容易 DP 了，可设 $f_{i,j}$ 表示考虑完了前 $i$ 个位置，目前左端点在 $i$ 之前且仍未覆盖的右端点最大值为 $j$，转移形如前缀乘、后缀查和单点加，直接用线段树维护即可，时间复杂度 $O((n+q)\log n)$。

• 区间连续段

在排列中的定义为 $\max-\min=r-l$ 的区间，感觉用处不大，可能有时会对连续段 DP。求区间连续段可以使用下述扫描线，复杂度 $O(n\log n)$，也存在析合树做法，不过 LCA 都说没啥用，不管了。

P8600 连号区间数

求排列的区间连续段数量。$n\le 5\times 10^4$，Bonus：$n\le 5\times 10^5$。考虑将条件移项，变为 $\max-\min-r+l=0$，同时有天然条件 $\max-\min-r+l\ge0$。

可以多次单调栈分别求出每个数左 / 右边第一个大于 / 小于其的位置，之后其作为最值的贡献矩形确定。$l,r$ 的贡献容易维护，直接上线段树扫描线，维护最小值及其个数，从而计算全局 $0$ 的个数即可。时间复杂度 $O(n\log n)$。

• 排列

这里不研究排序分析和置换，主要研究排列相关的 DP 之类。

P8376 [APIO2022] 排列

题意

构造尽可能短的排列 $p$，使得其上升子序列个数恰为 $k$。$k\le 10^{18}$，要求构造出的长度 $n\le 90$。

题解

事实上属于构造题范畴，这种构造数值的问题一般要考虑怎么进行基础操作，比如加 $1$ 和乘 $2$ 之类，从而构造出任意值。比如本题中若已有个数为 $x$ 的排列，则在其结尾添最小值可得到 $x+1$，添最大值可得到 $2x$，这样从高位构造到低位即可做到不超过 $2\log_2k$ 的次数。

然而还需要更少，但乘 $2$ 已经是增多的极大值了，难以优化，考虑对加 $1$ 下手。注意到整个排列可以分成两个子序列，分别是加一的递减序列和乘二的递增序列。在该结构结尾添加序列次小值时，得到的是 $x+2$，同样添加第三小值可得 $x+3$。

由于有乘 $2$ 操作，加 $2$ 是没用的，而加 $3$ 可以一次添加两个 $1$，且最小值和次小值相对位置不变，仍然可以继续加 $3$，这样就可以在加三次 $1$ 后每两位使用至多 $3$ 个新元素处理。这样总次数的量级降到了 $1.5\log_2 n$，细致分析一下的话第一个加 $1$ 不需要操作，且乘 $2$ 次数本来就少 $1$，不会超过 $90$ 次，可以通过。

P5999 [CEOI 2016] kangaroo

题意

给定 $p_1$ 和 $p_n$，求有多少种这样的排列满足 $\forall i\in[2,n-1],[p_{i-1}<p_i]=[p_{i+1}<p_i]$。取模，$n\le 2000$。

题解

如果从左到右考虑，只能记录最后一个数在前面的相对排名，导致难以确定开头为 $s$。因此按值从小到大考虑，并维护当前连续段数量，注意除开头结尾的边界均应比内部低，从而之后合成一段。

因此设 $f_{i.j}$ 表示考虑了 $[1,i]$ 内的数，当前有 $j$ 个连续段的方案数，转移可以单开一段或合并两个段。对 $s,t$ 需要特判放在开头结尾，这表现为只能在固定位置新开一段，或直接接在对应段上。此处直接接上虽然不满足比内部小，但其实固定为边界就不用满足了。总复杂度 $O(n^2)$。

P9197 [JOI Open 2016] 摩天大楼 / Skyscraper

题意

给定序列 $a$，求 $\sum_{i=1}^{n-1} \left|a_{p_i}-a_{p_{i+1}}\right|\le L$ 的排列 $p$ 数量。取模，$n\le 100,L\le 1000$。

题解

同样从小到大考虑，这样可以拆贡献，把差的绝对值拆到值域上，每经过一个单位长度就产生大概两倍段数的贡献。此处端点不贡献，因此需要记录已有端点的个数。于是设 $f_{i,j,k,o}$ 表示考虑了前 $i$ 小的数，当前形成 $j$ 个连续段，目前贡献 $k$，且已有 $o$ 个端点的方案数。

转移时讨论接在某个段上 / 新开一段 / 合并两段三种情况即可，注意均不能对已确定端点的位置操作，有多处需要减去 $o$。细节此处略去，时间复杂度 $O(n^2L)$。

这两题均是维护连续段个数，并以插入方式转移。这类问题通常可以画出示意图，之后考虑每个状态会对转移造成影响的量，只记录这些从而简化状态。例如这两题按值考虑后只需关注横线下的段数，因此只考虑段数即可。

CF2066D2 Club of Young Aircraft Builders

题意

给出长为 $m$ 的序列 $a$，要求将其中的 $0$ 替换为 $[1,n]$ 内的任意数，要求 $n$ 出现 $c$ 次，且 $\forall i\in[1,m],\sum_{j\le i}[a_j\ge a_i]\le c$。多组数据，$n,c\le 100,\sum m\le 10^4$。

题解

这题其实不是排列，但思路跟上面的题有共同点。D1 中 $a$ 数组全 $0$，显然可以从大到小依次填数，每次都填在前 $c$ 个内即可。然而这做不了有限制的情况，需要换一种做法。多种尝试后发现可以变为从小到大填数，则 $1$ 一定要填在前 $c$ 个内，若填了 $j$ 个，则填 $2$ 时可忽略这些位置。这等价于一定要填在前 $(j+c)$ 内，以此类推。

这时根据上题中的思路，已填的个数是唯一影响转移的量，因此只记这个就行。设 $f_{i,j}$ 表示考虑了前 $i$ 种值，总共填了 $j$ 个数的方案数。转移时可在前 $(j+c)$ 个位置内填，且一定要填上限制该数的所有位置。枚举填的个数 $k$，剩余位置的方案容易用组合数计算。时间复杂度为 $O(nmc)$，可以通过。总之还是要找转移所需的量维护在状态内。