先总结一些充要条件。
一个人 \(i\) 选不到自己的 \(a_i\) 的充要条件为：若为左侧，则存在左侧的一个 \(j\) 满足 \(a_k\in[j,i]\) 且 \(b_k=R\) 的 \(k\) 的个数 \(> i-j\)，右侧同理，满足其一即可。
一个方案不合法的充要条件为，若对于一个 \(b_i=R\) 的 \(i\)，\(i\) 选位置时 \([a_i,n]\) 都已被选。
发现如果我们已经确定了前 \(i-1\) 个人最终到达的位置，把被选的位置看作 \(1\)，未被选的位置看作 \(0\)，还是假设 \(b_i=R\)，此时如果 \(a_i\) 已经被选择，\(i\) 最终一定会选择 \(a_i\) 所在连续 \(1\) 段右侧的那个 \(0\) 位置。
所以每填一个最终选择的位置，我们都可以动态维护下每个 \(0\) 位置的方案数权重和贡献权重，然后考虑填哪一个 \(0\) 位置即可。
但此时的状态描述还是复杂的，考虑能不能简化状态信息。
较大的 \(n\) 限制了如果我们要设状态的话，状态中只能有位置个数和人数两个信息。那就考虑设 \(dp_{i,j}\) 表示前 \(i\) 个位置填了存在编号的 \(j\) 个人的方案数，\(f_{i,j}\) 表示此时的贡献和，则显然 \(i\ge j\)。
考虑当 \(i>j\) 时，必然存在一个位置未填写，考虑枚举最后一个空位的位置 \(k\)，我们可以以该空位为分割划分子问题，有转移方程：
需要注意一些边界条件，比如 \(dp_{0,0}=1\)。
当 \(i=j\) 时，我们不妨枚举最后一个人最终填的位置，由于最后一个人填的时候，左右两侧都已填满，所以最后一个人实际可以填到任意一个位置上，并且填在空位上时可以朝任意一个方向，共 \(i+1\) 种不同的决策，转移方程为：
时间复杂度 \(O(n^3)\)。
基于子问题的划分，思考状态的设计与转移。子问题的划分通常可以考虑最后一个决策的选取。