1 Loop Bubble Sort 题解

编号：AT_arc187_c
tag：计数 dp
难度：\color{orange}{2574}

“冒泡排序有一种被出烂但是每次碰到我都不会的美感。” —— wosile

该题只要求一轮冒泡排序，然后考虑一轮冒泡排序的效益实际上是把一段最大值在第一个元素的段把最大值放到了最后面，然后要求这若干段的最大值递增。

这很好考虑啊！那实际有用的状态发现只有当前段的 \max 而已。那么钦定 f_{i,j} 表示第 i 个元素所在联通块 \max 为 j 的方案数。为了方便相邻段转移，所以再钦定 g_{i,j} 表示第 i 个元素所在联通块 \max 为 j，且第 i 个元素为当前联通块最后一个元素的方案数。

接下来会发现统计经过一轮变化后的排列要比统计原排列要轻松简单。因为经过一轮变化后的排列的每个元素实际位置恰好对应了给定序列的位置。如果序列全为 -1 那是较为简单的。现在有了给定元素之后约束比较麻烦，那么就来细致刻画约束。

往 f_{i,j} 转移，也就是在 w=(j-1)-(i-1)-(\sum[a_k\lt j])+(\sum_{1\le k\lt i}[a_k\lt j]) 个元素中任意选出一个作为当前值。若当前位置已被钦定，那么除了 a_k\ge j 的情况无法转移，其余转移系数为 1；否则转移系数为 w。

往 g_{i,j} 转移，那么当前 a 只能被钦定为 j。所以要特判一下 a_i\neq j 和 pos_j\neq i 的情况。转移系数为 1。

从 f_{i-1,j} 可以直接 \Theta(1) 转移，从 g_{i-1,p}(p\lt j) 前缀和优化可以将 \Theta(n) 转移优化到 \Theta(1)。

状态数 \Theta(n^2)，转移 \Theta(1)。