【组合对象】序列问题

Note: This is just a simple note in class.
Full ver will be written later.

摘要

离散化
极小字符集序列的刻画

离散化

AGC006D

01序列，变化一个 bit

观察前后 -> 得出 bit

O(n log n) 二分 / O(n) 线性

一个冒泡

if is_sorted() break
for i in [1,n-1] swap if a[i]>a[i+1]
for i in [n-1,1] swap if a[i]>a[i+1]
for i in [1,n-1] swap if a[i]>a[i+1]

给定序列求排序所需轮数

(P4375: 只有前两个)

最前面 1 往后放最后面 0 往前放

【前缀与后缀】：单调性

回到原序列，单点修改，维护变化过程

区间数据结构

进一步地，01 序列 -> 二维平面路径

每次冒泡：修改阶梯

两条线移动

括号序列

刻画：前缀和、折线、方格走路…

P7323

观察发现，如果存在一条 $x \to y$ 的合法路径，那么一定存在 $y \to x$ 的合法路径。

如果存在 $x \to y, y \to z$ 的合法路径，那么一定存在 $x \to z$ 的合法路径。

合法路径具有自反性和传递性。由上我们可以得出最终互相能形成合法路径的点形成一个团。我们现在要做的就是求出所有团，答案即为 $\sum (\binom{s_{i}}{2})$ 。其中 $s_{i}$ 为团的大小。

我们发现，如果 $x$ 到某团内有一条边，其权值与 $y$ 到该团内的一条边相等，那么 $x, y$ 就可以被合并。

不妨设计这样一个算法：初始每个点自己是一个团。

然后看这些团的入边，如果存在两个权值相同的边，就把他们的起点合并。

如此一直合并直到不能合并为止。

合并使用启发式合并，合并完之后可能会产生新的两个权值相同的入边，进行队列等待继续处理即可。

P11236

按照谷分成若干座山

CF1503F

按照括号的匹配关系进行连边。

CF1685C

前缀和。看成折线：翻转就是中心对称。

CF1458D

P6672

区间最值

基本结构是笛卡尔树。

区间连续段【排列】

刻画方式：

$max - min = r - l$

求数量：扫描 $r$ ，线段树维护 $l$ 上式的值

max 和 min 可以边维护单调栈边计算贡献

然后我们要计算 “0” 的数量，由于上式的值一定为非负数，所以我们可以维护区间最小值以及最小值数量。

排列

P8376

画图像以快速理解。

我们考虑不断往末尾追加元素：

考虑追加一个比当前元素都大的数：这个时候，上升子序列个数会 $\times 2$ 。

考虑追加一个比当前元素都小的数：这个时候，上升子序列个数会 $+ 1$ 。

我们联想到：对于一个数，将它转为二进制，则可以发现它可以通过不断的 $+ 1$ 和 $\times 2$ 凑出来，两者分别对应了将末尾位设为 $1$ 以及左移一位。

如此我们便可以得到一个操作次数上界大约为 $2 \log k$ 的算法，更准确地说，是 $⌊ \log k ⌋ + 1 + popcount (k)$ 的。

可以获得 $90$ 左右的分数，不可否认的是这个分数在 APIO 场上已经令人满意了，此时可以直接丢掉这一题。下面我们来想正解：

$2 \log k$ 操作次数在 $120$ 左右，我们联想一下会发现 $1.5 \log k$ 和 $90$ 差不多！

考虑 $\times 2$ 的操作很难再优化了，于是我们不妨从 $+ 1$ 这里入手。

可以发现，如果我们能够把二进制下相邻两个 1 合并在一块处理，那么总的处理次数会变成 $0.5 \log k$ ，就达到了我们想要的 $1.5 \log k$ 操作次数！

实际上一个如下的图形满足了条件：

（总共新增 $3$ 个上升子序列）

需要注意的是，如果我们找不到前面的两个陪衬点，就不能一次性操作了。

如上，便可完成本题正解。

排列上的 dp

P5999

数“锯齿状”排列个数，即，不存在 $p_{i - 1} < p_{i} < p_{i + 1}$ 或 $p_{i - 1} > p_{i} > p_{i + 1}$ 。首尾给定。

我们考虑从小往大放数，此时会形成若干个合法连续段，我们考虑在 dp 中维护这些合法连续段。

设 $d p_{i, j}$ 为考虑了 $1 \sim i$ 的数，形成了 $j$ 个连续段所需要的方案数。

分为以下几种方案：

开一个新的段。若我们正在加入 $i + 1$ ，从 $d p_{i, j}$ 转移而来，那么现在就有 $j + 1$ 个可供选择的地方。特别地，如果 $i + 1 > s$ ，那么代表序列头部已经确定完毕，头部不能再加入，于是可供选择的地方少一个。对于序列尾部也是如此。那么就是： $d p_{i, j} \times (j + 1 - [i > s] - [i > t]) \to d p_{i + 1, j + 1}$ 。
在段两边加元素？这样子会导致段变得不合法，后面我们会证明不需要使用这种操作。
将两个段合并。由于两边元素都比 $i + 1$ 小，所以合并之后段仍然合法。 $d p_{i, j} \times (j - 1) \to d p_{i + 1, j - 1}$ 。

下面我们来看看这个算法为什么是对的，它的本质是什么。

我们把排列看成 $(i, p_{i})$ 拍到平面直角坐标系中。（以下对应排列 $[2, 3, 1, 7, 4, 6, 5]$ ）

蓝线从下往上扫。遇到这种凹陷的点就相当于新开一个段。

遇到这种向上凸起的点，就相当于把左右两边合并。

如此，蓝线下面被分成了若干个段，每次向上扫要么新开段，要么合并两个段。

这个算法本质上就是在维护蓝线从下往上扫的过程。由此我们不难得出每个排列都能通过上述方式生成，且在计数中不重不漏。

摘要

离散化