考虑最终序列上的一对匹配 $(u,v)$（$u < v$）：

• 如果 $u$ 从始至终都没被操作过那么一定合法，因为会把 $u$ 爆掉的操作一定发生在 $u$ 前面，而 $u$ 换不回去；
• 如果 $u$ 被操作过（称为关键点），考虑最后一次击杀的是 $x$，那么 $v$ 只有可能是 $x$（也可能也不合法），同样因为这次操作之后穿过 $u$ 的操作只有从后往前。

我们可以暴力把图建出来，设关键点 $u$ 的 $p_u$ 为这个唯一可能的 $v$（没有则为 $0$），可以观察到：

• 对于关键点 $u$，$p_u \ne 0$，那么对于关键点 $u < x < p_u$ 一定有 $p_x \in \{0,p_u\}$。

因为 $x$ 一定是在 $u$ 最后一次操作过后，通过 $p_u$ 进入区间的。如果没在区间内交换那只可能 $p_x=p_u$，出问题只可能是区间内和另一个 $y$ 交换了，而我们发现在 $y$ 进入区间的时候其实已经把和 $x$ 的边 ban 掉了。

所以我们相当于能划分成一些区间 $[l,r)$ 满足区间内的 $p_i \in \{0,r\}$，设 $f_{i,j,0/1}$ 表示后缀 $i$ 有 $j$ 个没匹配，$r$ 有没有被匹配的答案，容易写出转移。

时间复杂度 $\mathcal O(nm+n^2)$，当然你可以动态维护一下被操作过的 $u$ 的 $p_u$，做到 $\mathcal O(m+n^2)$。