题解

思路

把两种选择分别记为左操作和右操作。

做法

枚举 $i<j$：若 $V_i\le V_j$，二者之间没有限制；若 $V_i>V_j$ 且 $P_i=P_j$，第 $j$ 次操作无论选哪边都会碰到更大的数，答案为 $0$。若 $V_i>V_j$ 且 $P_i<P_j$，则第 $i$ 次必须选左、第 $j$ 次必须选右；当 $P_i>P_j$ 时方向恰好相反。为每次操作记录尚未确定、必须向左或必须向右，传播所有操作对给出的要求，出现冲突时答案也是 $0$。

若没有冲突，这些成对条件已经足以保证所有操作可行；方向已确定的操作只有一种选择，仍未确定的每次都有两种选择。设未确定的操作数为 $k$，答案即为 $2^k\bmod 998244353$。

复杂度

时间复杂度为 $O(Q^2)$，空间复杂度为 $O(Q)$。