解题思路

从左向右找到第一个 $p_i\ne q_i$ 的位置 $l$，从右向左找到最后一个不相等的位置 $r$。若整段都相等，则 $l=r=0$，对应把长度为 1 的区间翻转（序列不变），答案为 1。

否则，检查把 $p[l..r]$ 翻转后是否恰好等于 $q[l..r]$：用两个指针同时从两端向中间走，判断 $p[\textit{left}]$ 是否等于 $q[\textit{right}]$。只要有一处对不上，说明这一段不是另一段的逆序，答案为 0。

若这一段翻转后已经对齐，则这一组 $[l,r]$ 是一种合法选择。还可以尝试把区间同时向两边扩张：当 $l-1\ge 0$、$r+1<n$ 且 $p_{l-1}=p_{r+1}$ 时，扩张后翻转仍然合法（外侧本来就已经与 $q$ 相等）。每成功扩张一次，答案加 1。

复杂度分析