3647.随机打乱
2026-09-13
题解
保证 2n 个端点互不相同,并且随机打乱意味着未处理的二元组成为下一个的概率均等。
观察限制,我们发现对于某个已添加的 ai ,它将区间分为两部分,对于完全落在 ai 左边的二元组 (aj,bj),其能否产生贡献只与 ai 左侧的点有关,对于右侧也一样。
对于跨过 ai 的区间,此后不会产生贡献。
这完全符合区间 DP 的结构,大区间被选中的点分割成两部分。
考虑设 f[l][r] 表示完全包含在开区间 (l,r) 中二元组对 ∣S∣ 的期望贡献。
我们记 (l,r) 完全包含 cnt(l,r) 个区间。
假设第一个处理 (ai,bi),其一定会造成贡献(此时 (l,r) 内没有任何点),加入后拆分成子问题,也就是说:
f[l][r]=cnt(l,r)1i∑(1+f[l][ai]⋅f[ai][r])
把 1 提出来,化简一下:
f[l][r]=1+cnt(l,r)1i∑(f[l][ai]+f[ai][r])
最终答案为 f[0][2n+1],时间复杂度 O(n3),无法通过。
我们发现枚举 l,r 时,可以通过固定 l,使 r 递增来进行增量维护,进而让复杂度降低到 O(n2)。
