Qoj1839 Joke

Qoj1839 Joke

题目要求对 $s$ 计数，而 $s$ 只跟 $p,q$ 的相对大小有关，所以我们先将 $p$ 排序，同时保证 $q$ 与 $p$ 的大小关系不变。

所以可以画出图像

黑线是 $a_1$，红点是 $a_2$。 所有在黑线下方的点都是 $s_i$ 为 $0$ 的点，上方都是 $s_i$ 为 $1$ 的点。

同时，连个方案不同当且仅当上面或下面的点集不一样（一个不一样了另一个肯定页不一样），所以可以只对下面的点集计数。

当我们选了一个点后，所有小于这个点的点一定都在 $p$ 的下方，即 $s_i$ 为 $0$（就是图中的阴影部分）。

发现选出来的点是前缀 $\max$ ，这是单调不降的（同时，不可能选比之前的点小的点），同时，我们可以根据前缀 $\max$ 还原出原来的覆盖区间，所以这两个东西等价，即构成双向映射，所以对点集计数等价于对覆盖区间计数，对覆盖区间计数等价于对前缀 $\max$ 计数。

因为 $a_1,a_2$ 离散化完后是 $p,q$，所以我们可以直接对 $q$ 计数，一定能构造出合法的 $a_1,a_2$。

所以现在我们就是要选出一个上升子序列，问方案数，可以设 $dp_{i,j,k}$ 表示前 $i$ 个数，有 $j$ 个未确定的值，最后一个数填 $k$ 的方案数，直接 dp。