Qoj1839 Joke

chenzhiyv · 2025-11-07 14:51:35 · 个人记录

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。