传送门：https://atcoder.jp/contests/agc065/tasks/agc065_b
考虑 $dp$ 从 $Q$ 得到 $P$ 的过程个数。每次当我们插入 $i$ 的时候，我们要保证 $[1,i]$ 中所有数在新的 $Q$ 中的相对位置关系和在 $P$ 中相同（因为之后它们的相对位置就改变不了了）；按顺序考虑每个 $i$ 要插入在哪里的话，必须要记录所有 $[1,i-1]$ 中的数的当前位置，这是不可行的，并且这一点难以被丢弃。
既然这样想走不通，正难则反，我们可以把整个过程反过来考虑，也就是说，从 $P$ 开始，顺次把 $n$~$1$ 重新插入，直到还原回 $Q$。这样做的话，我们要保证的事还是相似，即，在插入 $i$ 之后，当前序列中 $[i,n]$ 的相对位置关系必须和在 $Q$ 中相同；但这次更好的是，我们利用了在上个做法中没有充分利用的条件，即 $Q$ 中元素是按大小顺序排列的。这样，想要保证当前序列中 $[i,n]$ 的相对位置关系和在 $Q$ 中相同，只需要记录在改变 $i$ 的位置前，$i+1$ 所处的位置，然后想办法转移就好了。
设 $dp_{i,j}$ 表示当前插入了 $[i,n]$ 中的数，$i$ 在序列中前面有 $j$ 个数（也就是说排第 $j+1$ 个）。此时，如果 $i-1$ 在 $i$ 前面的 $j$ 个数之内，那么它在下一步的插入中就有 $j$ 种位置选择，反之则有 $j+1$ 种；此时，由于比 $i$ 大的所有数都被移到 $i$ 后面去了，所以它之前的 $j$ 个数一定都比它小，且它们还没被操作（也就是说相对顺序还没改变）；因此，一旦 $i、j$ 确定了，那么这 $j$ 个数具体是什么也确定了（就是原序列中前 $j$ 个小于 $i$ 的数）；我们可以预先求出 $i-1$ 在所有小于 $i$ 的数中的位置排名，这样就可以 $O(1)$ 判断它是否在 $j$ 个数内。
于是，设 $i-1$ 在所有小于 $i$ 的数中的位置排名为 $rk_i$，那么 $dp_{i,j}$ 会向后转移到所有 $dp_{i-1,k}(0\leq k\leq j-[rk_i<=j])$，暴力单次转移复杂度 $O(n)$，使用差分可以降至 $O(1)$。整体时间复杂度 $O(n^2)$。